求次短路。
1 // File Name: 3255.cpp 2 // Author: Missa 3 // Created Time: 2013/4/5 星期五 1:01:09 4 5 #include<iostream> 6 #include<cstdio> 7 #include<cstring> 8 #include<algorithm> 9 #include<cmath> 10 #include<queue> 11 #include<stack> 12 #include<string> 13 #include<vector> 14 #include<cstdlib> 15 #include<map> 16 #include<set> 17 using namespace std; 18 #define CL(x,v) memset(x,v,sizeof(x)); 19 #define R(i,st,en) for(int i=st;i<en;++i) 20 #define LL long long 21 #define inf 0x3f3f3f3f 22 23 const int maxn = 5e3+5; 24 int n,m; 25 struct edge 26 { 27 int v, c; 28 edge(){} 29 edge(int v, int c):v(v), c(c){} 30 }; 31 vector <edge> adj[maxn]; 32 33 int dij(int src) 34 { 35 bool vis[maxn][2]; 36 CL(vis,0); 37 int dis[maxn][2]; 38 int u,v,c; 39 CL(dis,0x3f); 40 dis[src][0] = 0; 41 for (int i = 0; i <= 2 * n; ++i) 42 { 43 int tmp = inf, u = src, p = 0; 44 for (int j = 1; j <= n; ++j) 45 { 46 if(!vis[j][0] && tmp > dis[j][0]) 47 { 48 tmp = dis[j][0]; 49 u = j; 50 p = 0; 51 } 52 else if(!vis[j][1] && tmp > dis[j][1]) 53 { 54 tmp = dis[j][1]; 55 u = j; 56 p = 1; 57 } 58 } 59 if(tmp == inf) break; 60 vis[u][p] = 1; 61 for (int j = 0; j < adj[u].size(); ++j) 62 { 63 v = adj[u][j].v; 64 c = adj[u][j].c; 65 if (dis[v][0] > tmp + c) 66 { 67 dis[v][1] = dis[v][0]; 68 dis[v][0] = tmp + c; 69 } 70 else if (dis[v][1] > tmp + c) 71 { 72 dis[v][1] = tmp + c; 73 } 74 } 75 } 76 return dis[n][1]; 77 } 78 79 int main() 80 { 81 int u, v, c; 82 while(~scanf("%d%d", &n, &m)) 83 { 84 CL(adj, 0); 85 while(m--) 86 { 87 scanf("%d%d%d",&u, &v, &c); 88 adj[u].push_back(edge(v,c)); 89 adj[v].push_back(edge(u,c)); 90 } 91 printf("%d\n",dij(1)); 92 } 93 return 0; 94 }