USACO Training Section 2.4 Bessie Come Home

英文原题  中文题译

加权图上的单源最短路径。本身是最简单的。题目加了一些限制，如，节点从a-z,A-Z编号，最后只输出大写编号的节点到Z节点的最短路径中最短的一个。

走了不少弯路，一开始想用邻接表做，后来一想，整个节点最多52个，应该用最简单的矩阵表示。Dijstraka算法也是用最简单的n^2实现，没有用优先队列来选取最小元素。在节点数大的时候，还是用优先队列实现合适。

/*
ID: blackco3
TASK: comehome
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_node_ 52
int n_node=_max_node_ ;
int dis[_max_node_][_max_node_] ;

int main() {
	freopen("comehome.in", "r", stdin);
	freopen("comehome.out", "w", stdout);
	int n_path, n1, n2, d ;
	cin >> n_path ;
	memset( dis, 0xff, sizeof(dis) );
	for( int i=0; i<n_path; i++ ){
		char v1, v2 ;
		cin >> v1 >> v2 >> d;
		if( v1==v2 )
			continue ;
		n1 = v1>='a' ? v1-'a' : v1-'A'+26 ;
		n2 = v2>='a' ? v2-'a' : v2-'A'+26 ;
		dis[n2][n1] = dis[n1][n2] = dis[n1][n2]==-1 || dis[n1][n2] > d ? d : dis[n1][n2] ; 
	}
	int sdis[_max_node_], used[_max_node_] ;
	memcpy( sdis, dis[n_node-1], sizeof(sdis) );
	memset( used, 0, sizeof(used) );
    for(int i=0; i<n_node-1; i++) {
		register int tmin = 0x7fffffff, sel_node=-1 ;
		for(int j=0; j<=n_node-1; j++ ) {
			if( used[j] || sdis[j]==-1 || tmin <= sdis[j] )
				continue ;
			tmin = sdis[j], sel_node = j ;
		} 
		if( sel_node==-1 )
			break ;
		used[sel_node] = 1;
		for(int j=0; j<n_node-1; j++) {
			if( dis[sel_node][j]==-1 ) 
				continue ;
			if( sdis[j]==-1 || sdis[sel_node] + dis[sel_node][j] < sdis[j] ) 
				sdis[j] = sdis[sel_node] + dis[sel_node][j];
		}
    }
	int min_dis=0x7fffffff, node_no;
	for( int i=26; i<n_node-1; i++ )
		if( sdis[i]!=-1 && min_dis>sdis[i] )
			min_dis=sdis[i], node_no=i ;
	cout << (char)('A'+(node_no-26)) << " " << min_dis << endl ;

	return 0;
}