题意：一个无向带权图，求任意两点间的最短路径。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1874
——>>本来，这就是简简单单的最短路径，可是！！！陷阱～～坑得没话说……两个点之间竟可有多条路直接连通……
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;const int maxn = 200 + 10;
const int INF = 1000000000;
int d[maxn][maxn], G[maxn][maxn];int main()
{int N, M, i, j, k, u, v, w, S, T;while(scanf("%d%d", &N, &M) == 2){for(i = 0; i < N; i++)for(j = 0; j < N; j++)G[i][j] = i == j ? 0 : INF;for(i = 0; i < M; i++) //建图{scanf("%d%d%d", &u, &v, &w);G[u][v] = G[v][u] = min(G[u][v], w); //最坑人的地方！！！}for(i = 0; i < N; i++) //赋初值for(j = 0; j < N; j++)d[i][j] = i == j ? 0 : INF;bool vis[maxn];for(i = 0; i < N; i++) //从i到任意点的最短距离{memset(vis, 0, sizeof(vis));for(j = 0; j < N; j++) //N次寻路{int x, y = INF;for(k = 0; k < N; k++)if(!vis[k] && d[i][k] <= y)y = d[i][x = k];vis[x] = 1;for(k = 0; k < N; k++)d[i][k] = min(d[i][k], d[i][x] + G[x][k]);}}scanf("%d%d", &S, &T);if(d[S][T] == INF) printf("-1\n");else printf("%d\n", d[S][T]);}return 0;
}今天学习SPFA，再来刷此题～～
#include <cstdio>
#include <queue>
#include <cstring>using namespace std;const int maxn = 2000 + 10;
const int maxm = 1000 + 10;
const int INF = 0x3f3f3f3f;
int head[maxn], nxt[maxm<<1], u[maxm<<1], v[maxm<<1], w[maxm<<1], d[maxn], S, T;
bool inq[maxn];void addEdge(int uu, int vv, int ww, int e){u[e] = uu;v[e] = vv;w[e] = ww;nxt[e] = head[uu];head[uu] = e;
}void SPFA(){memset(inq, 0, sizeof(inq));memset(d, 0x3f, sizeof(d));d[S] = 0;queue<int> qu;qu.push(S);while(!qu.empty()){int x = qu.front();qu.pop();inq[x] = 0;for(int e = head[x]; e != -1; e = nxt[e]) if(d[v[e]] > d[x] + w[e]){d[v[e]] = d[x] + w[e];if(!inq[v[e]]){qu.push(v[e]);inq[v[e]] = 1;}}}
}int main()
{int N, M, i, uu, vv, ww;while(scanf("%d%d", &N, &M) == 2){memset(head, -1, sizeof(head));for(i = 0; i < M; i++){scanf("%d%d%d", &uu, &vv, &ww);addEdge(uu, vv, ww, 2*i);addEdge(vv, uu, ww, 2*i+1);}scanf("%d%d", &S, &T);SPFA();int ret = (d[T] == INF) ? -1 : d[T];printf("%d\n", ret);}return 0;
}