本文共 1460 字，大约阅读时间需要 4 分钟。
#include #include #include #include #include #include using namespace std; #define INF 0x7f7f7f7f int N, cnt, beg, end, v; int g[155][155], res[155]; char s[33], e[33]; map mp; struct Bus { int pos, val; Bus ( int x = 0, int y = 0 ) { pos=x, val=y; } bool operator < ( const Bus &t ) const { return val > t.val; } }; int getId ( char *p ) { if ( mp.count ( p ) == 0 ) { return mp[p] = cnt ++; } return mp[p]; } void init () { mp.clear (); cnt = 1; memset ( g, 0x7f, sizeof ( g ) ); memset ( res, 0x7f, sizeof ( res ) ); } bool read () { scanf ( "%d", &N ); if ( N == -1 ) return false; scanf ( "%s%s", s, e ); beg = getId ( s ); end = getId ( e ); for ( int i = 0; i < N; ++ i ) { scanf ( "%s%s%d", s, e, &v ); int x = getId ( s ), y = getId ( e ); g[x][y] = min ( g[x][y], v ); g[y][x] = min ( g[y][x], v ); } return true; } int DIS () { res[beg] = 0; priority_queue < Bus > q; q.push ( Bus ( beg, 0 ) ); while ( !q.empty () ) { Bus t = q.top (); q.pop (); if ( t.pos == end ) return t.val; for ( int i = 1; i < cnt; ++ i ) { if ( g[t.pos][i] != INF ) { if ( t.val + g[t.pos][i] < res[i] ) { res[i] = t.val + g[t.pos][i]; q.push ( Bus ( i, res[i] ) ); } } } } return -1; } void prs () { printf ( "%d\n", DIS () ); } int main() { while ( init(), read () ) { prs (); } return 0; }
转载于:https://www.cnblogs.com/tangcong/archive/2011/07/28/2119949.html