3049: 城市交通路网 Dijkstra

解题思路:单源最短路径， 寻找最小未确定最短距离节点t 更新所有节点最短距离

注意事项:一项测试数据有误

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], d[N],st[N],path[N],ans[N]; 
int main()
{
	int n;
	cin >> n;
	memset(d,0x3f,sizeof d);
	memset(a,0x3f,sizeof a);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++){
			int x;
			cin >> x;
			if(x != 0) a[i][j] = x;
		}
	d[1] = 0;
	for(int i = 0; i < n; i ++){
		int t = -1;
		for(int j = 1; j <= n; j ++ ){
			if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
		}
		st[t] = true;
		for(int j = 1; j <=n; j ++){
			if(d[j] > d[t] + a[t][j]){
				d[j] = d[t] + a[t][j];
				path[j] = t;
			}
		}
	}

	cout <<"minlong=" << d[n] << endl;
	int k = n, i = 1;	
	ans[i ++] = n;
	while(k != 1) {
		ans[i ++] = path[k];
		k = path[k]; 
	}
	while(--i) cout << ans[i] << ' ';
	
	return 0;
}