poj 3255(次短路)

题意:给一张无向带权图,让你求总1-n的次短路。

思路:好久没写dij了这次敲一边果然敲错了。。。这题就是在dis上加一维dis[i][0]记录最短路dis[i][1]记录次短路。就和我们在一个数组中找最小值次小值的原理差不多。我们只需先更新最小值,更新好了不要忘了再用原来的最小值去更新次小值(我就忘了这个wa了2次)。然后在更新次小值。

代码如下:

poj 3255(次短路)
 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-01-27 15:21
 5  * Filename     : poj_3255.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 50010;
34 int n, m, dis[LEN][2];
35 vector<pii> Map[LEN];
36 struct S{
37     int d, v, f;
38 };
39 S MS(int d, int v, int f){S ret;ret.d = d;ret.v = v;ret.f = f;return ret;}
40 struct cmp{
41     bool operator() (S a, S b){return a.d > b.d;}
42 };
43 
44 void Dijkstra(int vex){
45     priority_queue<S, vector<S>, cmp> q;
46     int vis[LEN][2] = {0};
47     memset(dis, 0x3f, sizeof dis);
48     dis[vex][0] = 0;
49     q.push(MS(dis[vex][0], vex, 0));
50     while(!q.empty()){
51         S nvex = q.top(); q.pop();
52         int nv = nvex.v, nf = nvex.f;
53         if(vis[nv][nf])continue;
54         vis[nv][nf] = 1;
55         for(int i=0; i<Map[nv].size(); i++){
56             int x = Map[nv][i].first, y = Map[nv][i].second;
57             if(dis[x][0] > dis[nv][nf] + y){
58                 dis[x][1] = min(dis[x][1], dis[x][0]);
59                 dis[x][0] = dis[nv][nf] + y;
60                 q.push(MS(dis[x][0], x, 0));
61             }
62             else if(dis[nv][nf] + y != dis[x][0] && dis[x][1] > dis[nv][nf] + y){
63                 dis[x][1] = dis[nv][nf] + y;
64                 q.push(MS(dis[x][1], x, 1));
65             }
66         }
67     }
68 }
69 
70 int main()
71 {
72     //freopen("in.txt", "r", stdin);
73     int a, b, val;
74     while(scanf("%d%d", &n, &m)!=EOF){
75         for(int i=0; i<LEN; i++)Map[i].clear();
76         for(int i=0; i<m; i++){
77             scanf("%d%d%d", &a, &b, &val);
78             Map[a].PB(MP(b, val));
79             Map[b].PB(MP(a, val));
80         }
81         Dijkstra(1);
82         printf("%d\n", dis[n][1]);
83     }
84     return 0;
85 }
View Code

poj 3255(次短路)

上一篇:ACM - ICPC World Finals 2013 I Pirate Chest


下一篇:HTTP 错误 404.3 – Not Found 由于扩展配置问题而无法提供您请求的页面。如果该页面是脚本,请添加处理程序。如果应下载文件,请添加 MIME 映射。