最短路水题，没啥好解释的。。
#include#include #include #include using namespace std; const int maxv=2333;const int INF=0x3f3f3f3f; int n,m; struct edge{ int from, to, cost; edge() {} edge(int _from, int _to, int _cost) { from = _from; to = _to; cost = _cost; }}; vector G[maxv];vector edges;int rank[maxv], dis[maxv];bool inque[maxv]; void add(int u, int v, int w) { edges.push_back(edge(u, v, w)); int m = edges.size(); G[u].push_back(m-1);} int spfa(int s, int n) { for (int i = 0; i <= n; i++) { dis[i] = INF; rank[i] = 0; inque[i] = false; } dis[s] = 0; rank[s] = 1; inque[s] = true; queue que; que.push(s); while (!que.empty()) { int u = que.front(); inque[u] = false; que.pop(); for (int i = 0; i < (int)G[u].size(); i++) { edge e = edges[G[u][i]]; if (dis[e.to] > dis[u] + e.cost) { dis[e.to] = dis[u] + e.cost; if (!inque[e.to]) { que.push(e.to); inque[e.to] = true; rank[e.to]++; if (rank[e.to] >= n) return false; } } } } return true;} int main(){ memset(dis,0x3f3f3f3f,sizeof(dis)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } if(spfa(1,m)) printf("%d\n",dis[m]); return 0;}