【dijkstra优化/次短路径】POJ3255-Roadblocks

（2）初始化时，源点的短边初始化为0，源点的次短边必须初始化为INF，而不是0。比如下面这组数据：

4 2
1 2 100
2 4 200
答案应该是500，然而如果初始化为0则答案会输出700。因为500的结果是又1到2，在从2返回1，再到2，再到4,100+100+100+200=500得到的；如果次短边初始化为0，则次短路径不再返回源点，而是在2与4之间折返，会偏大。
（3）53行绝对不能直接赋值，而是要swap！因为最短边被修改后，它的值是要留给次短边的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int INF=0x7fffffff;
 8 const int MAXN=100000+10;
 9 struct Rec
10 {
11     int num,len;
12     bool operator < (const Rec &a) const
13     {
14         return len>a.len;
15        
16     }
17 }; 
18 int u[MAXN*2],v[MAXN*2],w[MAXN*2];
19 
20 int dis[MAXN/2],secondis[MAXN/2];
21 
22 int first[MAXN/2],next[MAXN*2];
23 int n,r;
24 
25 void dijkstra()
26 {
27     priority_queue<Rec> que;
28     
29     for (int i=1;i<n;i++)
30     {
31          dis[i]=INF;
32          secondis[i]=INF;
33     }
34     dis[0]=0;
35     secondis[0]=INF;
36     
37     Rec temp;
38     temp.len=0;temp.num=0;
39     que.push(temp);
40     
41     while (!que.empty())
42     {
43         Rec head=que.top();
44         que.pop();
45         if (head.len>secondis[head.num]) continue;
46         
47         int k=first[head.num];
48         while (k!=-1)
49         {
50             int d=head.len+w[k];
51             if (dis[v[k]]>d)
52             {
53                 swap(dis[v[k]],d);
54                 temp.len=dis[v[k]];temp.num=v[k];
55                 que.push(temp);
56                
57             }
58             if (dis[v[k]]<d && secondis[v[k]]>d)
59             {
60                 secondis[v[k]]=d;
61                 temp.len=secondis[v[k]];temp.num=v[k];
62                 que.push(temp);
63                
64             }
65             k=next[k];
66         }
67     }
68 }
69 
70 int main()
71 {
72     scanf("%d%d",&n,&r);
73     
74     memset(first,-1,sizeof(first));
75     for (int i=0;i<r;i++)
76     {
77         scanf("%d%d%d",&u[i],&v[i],&w[i]);
78         u[i]--;
79         v[i]--;
80         next[i]=first[u[i]];
81         first[u[i]]=i;
82         
83         v[i+r]=u[i];
84         u[i+r]=v[i];
85         w[i+r]=w[i];
86         next[i+r]=first[u[i+r]];
87         first[u[i+r]]=i+r;
88        
89     }
90     dijkstra();
91     cout<<secondis[n-1]<<endl;
92     system("pause");
93     return 0;
94 }

【dijkstra优化/次短路径】POJ3255-Roadblocks

标签：