COGS——T 826. [Tyvj Feb11] GF打dota

http://www.cogs.pro/cogs/problem/problem.php?pid=826

★★☆ 输入文件：dota.in 输出文件：dota.out 简单对比
时间限制：1 s 内存限制：128 MB

众所周知，GF同学喜欢打dota，而且打得非常好。今天GF和Spartan同学进行了一场大战。

现在GF拿到一张地图，地图上一共有n个地点，GF的英雄处于1号点，Spartan的基地位于n号点，

GF要尽快地选择较短的路线让他的英雄去虐掉Spartan的基地。但是Spartan早就料到了这一点，

他有可能会开挂(BS~)使用一种特别的魔法，一旦GF所走的路线的总长度等于最短路的总长度时，

GF的英雄就要和这种魔法纠缠不休。这时GF就不得不选择非最短的路线。现在请你替GF进行规划。

对于描述的解释与提醒：

1.无向路径，花费时间当然为非负值。

2.对于本题中非最短路线的定义：不管采取任何迂回、改道方式，

只要GF所走的路线总长度不等于1到n最短路的总长度时，就算做一条非最短的路线。

3.保证1~n有路可走。

输入：

第一行为n，m(表示一共有m条路径)
接下来m行，每行3个整数a，b，c，表示编号为a,b的点之间连着一条花费时间为c的无向路径。
接下来一行有一个整数p，p=0表示Spartan没有开挂使用这种魔法，p=1则表示使用了。

输出：

所花费的最短时间t，数据保证一定可以到达n。

样例输入1：
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
0

样例输入2：
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
1

样例输出1：

样例输出2：

对于50%的数据，1<=n,m<=5000
对于70%的数据，1<=n<=10000, 1<=m<=50000,p=0,
对于100%的数据，1<=n<=10000, 1<=m<=50000,p=1
无向图，花费时间c>=0

各个测试点1s

来源：lydliyudong Tyvj February二月月赛第二场第2道

最短路+次短路（练A*了、、）

  1 #include <cstdio>
  2 #include <queue>
  3 
  4 const int INF(0x3f3f3f3f);
  5 const int N(10005);
  6 const int M(50005);
  7 int hed[N],had[N],sumedge;
  8 struct Edge
  9 {
 10     int v,next,w;
 11 }edge1[M<<1],edge2[M<<1];
 12 inline void ins(int u,int v,int w)
 13 {
 14     edge1[++sumedge].v=v;
 15     edge1[sumedge].next=hed[u];
 16     edge1[sumedge].w=w;
 17     hed[u]=sumedge;
 18     edge2[sumedge].v=u;
 19     edge2[sumedge].next=had[v];
 20     edge2[sumedge].w=w;
 21     had[v]=sumedge;
 22     
 23     edge1[++sumedge].v=u;
 24     edge1[sumedge].next=hed[v];
 25     edge1[sumedge].w=w;
 26     hed[v]=sumedge;
 27     edge2[sumedge].v=v;
 28     edge2[sumedge].next=had[u];
 29     edge2[sumedge].w=w;
 30     had[u]=sumedge;
 31 }
 32 
 33 int dis[N];
 34 bool inq[N];
 35 inline void SPFA(register int s)
 36 {
 37     for(int i=1;i<s;i++) dis[i]=INF;
 38     dis[s]=0; inq[s]=1;
 39     std::queue<int>que; que.push(s);
 40     for(int u,v;!que.empty();)
 41     {
 42         u=que.front(); que.pop(); inq[u]=0;
 43         for(int i=had[u];i;i=edge2[i].next)
 44         {
 45             v=edge2[i].v;
 46             if(dis[v]>dis[u]+edge2[i].w)
 47             {
 48                 dis[v]=dis[u]+edge2[i].w;
 49                 if(!inq[v]) que.push(v),inq[v]=1;
 50             }
 51         }
 52     }
 53 }
 54 
 55 struct Node
 56 {
 57     int now,g;
 58     bool operator < (Node a) const
 59     {
 60         return a.g+dis[a.now]<g+dis[now];
 61     }
 62 };
 63 inline int Astar(int s,int t,int k)
 64 {
 65     std::priority_queue<Node>que; Node u,v;
 66     u.now=s; u.g=0; que.push(u); int cnt=0;
 67     for(;!que.empty();)
 68     {
 69         u=que.top(); que.pop();
 70         if(u.now==t) cnt++;
 71         if(cnt==k) return u.g;
 72         for(int i=hed[u.now];i;i=edge1[i].next)
 73         {
 74             v.now=edge1[i].v;
 75             v.g=u.g+edge1[i].w;
 76             que.push(v);
 77         }
 78     }
 79 }
 80 
 81 inline void read(int &x)
 82 {
 83     x=0; register char ch=getchar();
 84     for(;ch>'9'||ch<'0';) ch=getchar();
 85     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
 86 }
 87 inline void write(int x)
 88 {
 89     if(x/10) write(x/10);
 90     putchar(x%10+'0');
 91 }
 92 int AC()
 93 {
 94     freopen("dota.in","r",stdin);
 95     freopen("dota.out","w",stdout);
 96     int n,m,p; read(n),read(m);
 97     for(int u,v,w;m--;ins(u,v,w))
 98         read(u),read(v),read(w);
 99     read(p);       SPFA(n);
100     write(Astar(1,n,p+1));
101     return 0;
102 }
103 
104 int I_want_AC=AC();
105 int main(){;}

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。