题意：给一张无向带权图，让你求总1-n的次短路。
思路：好久没写dij了这次敲一边果然敲错了。。。这题就是在dis上加一维dis[i][0]记录最短路dis[i][1]记录次短路。就和我们在一个数组中找最小值次小值的原理差不多。我们只需先更新最小值，更新好了不要忘了再用原来的最小值去更新次小值（我就忘了这个wa了2次）。然后在更新次小值。
代码如下：
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 }