loj 1099(最短路）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25956

思路：dist[v][0]代表走到点v的最短路，dist[v][1]代表走到点v的次短路（dist[v][0]!=dist[v][1]),然后Dijkstra更新就可以了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<vector>
 7 using namespace std;
 8 #define MAXN 5555
 9 #define MAXM 555555
10 #define inf 1<<30
11 #define FILL(a,b) memset(a,b,sizeof(a))
12 
13 struct Edge{
14     int v,w,next;
15 }edge[MAXM];
16 
17 int n,m,NE;
18 int head[MAXN];
19 
20 void Insert(int u,int v,int w)
21 {
22     edge[NE].v=v;
23     edge[NE].w=w;
24     edge[NE].next=head[u];
25     head[u]=NE++;
26 }
27 
28 int dist[MAXN][2];
29 int Dijkstra()
30 {
31     for(int i=1;i<=n;i++)
32         for(int j=0;j<=1;j++)dist[i][j]=inf;
33     priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;
34     que.push(make_pair(0,1));
35     dist[1][0]=0;
36     while(!que.empty()){
37         pair<int,int>p=que.top();
38         que.pop();
39         for(int i=head[p.second];i!=-1;i=edge[i].next){
40             int v=edge[i].v,w=edge[i].w;
41             if(p.first+w<dist[v][0]){
42                 dist[v][1]=dist[v][0];
43                 dist[v][0]=p.first+w;
44                 que.push(make_pair(dist[v][0],v));
45             }else if(p.first+w!=dist[v][0]&&p.first+w<dist[v][1]){
46                 dist[v][1]=p.first+w;
47                 que.push(make_pair(dist[v][1],v));
48             }
49         }
50     }
51     return dist[n][1];
52 }
53 int main()
54 {
55     int _case,t=1;
56     scanf("%d",&_case);
57     while(_case--){
58         scanf("%d%d",&n,&m);
59         NE=0;
60         FILL(head,-1);
61         while(m--){
62             int u,v,w;
63             scanf("%d%d%d",&u,&v,&w);
64             Insert(u,v,w);
65             Insert(v,u,w);
66         }
67         printf("Case %d: %d
",t++,Dijkstra());
68     }
69     return 0;
70 }

View Code