求一點到另外一點的最短距離,用SPFA即可得解。
P.S. 記得紀錄每個邊可以對點去分群,這樣在更新最短路徑的速度會比較快,如果沒做很容易TLE。
C++(0.100)
/*******************************************************/ /* UVa 10986 Sending email */ /* Author: LanyiKnight [at] knightzone.studio */ /* Version: 2016/10/16 */ /*******************************************************/ #include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; const int UNREACHABLE = -1; struct Edge{ int from; int to; int w; Edge(){} Edge(int _from, int _to, int _w){ from = _from; to = _to; w = _w; } }; int main(){ int N; while( scanf("%d", &N) != EOF ){ int n, m, S, T; for( int testcase = 1 ; testcase <= N ; ++testcase ){ scanf("%d%d%d%d", &n, &m, &S, &T); vector<int> shortestPath(n, UNREACHABLE); shortestPath[S] = 0; vector< vector<Edge> > nodeEdges = vector< vector<Edge> >(n, vector<Edge>()); int a, b, w; for( int i = 0 ; i < m ; ++i ){ scanf("%d%d%d", &a, &b, &w); nodeEdges[a].push_back( Edge(a, b, w) ); nodeEdges[b].push_back( Edge(b, a, w) ); } queue<int> next; vector<bool> inQueue(n, false); next.push(S); while( !next.empty() ){ int current = next.front(); next.pop(); inQueue[current] = false; for( int i = 0 ; i < nodeEdges[current].size() ; ++i ){ int toNode = nodeEdges[current][i].to; if( shortestPath[toNode] == UNREACHABLE || shortestPath[current] + nodeEdges[current][i].w < shortestPath[toNode] ){ shortestPath[toNode] = shortestPath[current] + nodeEdges[current][i].w; if( !inQueue[toNode] ){ next.push(toNode); inQueue[toNode] = true; } } } } printf("Case #%d: ", testcase); if( shortestPath[T] == UNREACHABLE ){ printf("unreachable\n"); } else{ printf("%d\n", shortestPath[T]); } } } return 0; }
回應