杭电 hdu 1874 畅通工程续
第二次
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://acm.hdu.edu.cn/showproblem.php?pid=1874Name : 1874 畅通工程续Date : Saturday, May 14, 2011Time Stage : 1 hours aroundResult:39530432011-05-14 10:57:25Accepted187415MS460K1462 BC++pyyTest Data:Review://----------------------------------------*/#include <iostream>#include <stdio.h>#include <string.h>using namespace std;const int size = 210, infinite = 0x0f0f0f0f;int city, path, from, to;int dist[size], map[size][size], hash[size];void dijkstra(){int i, j, k;memset( hash, 0, sizeof(hash) );for( i = 0; i < city; ++i )dist[i] = map[i][to];hash[to] = 1;dist[to] = 0;// 这句不加，就一直WAfor( i = 0; i < city; ++i ){int minPath = infinite;int iMinPath = 0;for( j = 0; j < city; ++j )if( !hash[j] && dist[j] < minPath ){iMinPath = j;minPath = dist[j];}hash[iMinPath] = 1;for( j = 0; j < city; ++j )if( !hash[j] && dist[iMinPath] + map[iMinPath][j] < dist[j] )dist[j] = dist[iMinPath] + map[iMinPath][j];}}int main(){int i, j, k, cost;while( cin >> city >> path ){memset( map, infinite, sizeof(map) );for( i = 0; i < path; ++i ){cin >> j >> k >> cost;map[j][k] = map[k][j] = min( map[j][k], cost );}cin >> from >> to;dijkstra();if( dist[from] == infinite )dist[from] = -1;cout << dist[from] << endl;}return 0;}