1030 Travel Plan (30 分)

1030 Travel Plan (30 分)

思路有空更新

#include <iostream>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int map[550][550], vis[550], dis[550], path[550];
int a[550][550], sum[550];
int n, m, S, D;
void dijkstra(int s){
    
	memset(dis, inf, sizeof dis);
	dis[s] = 0;
	for(int i = 0; i < n; ++i){
    
		int t = -1;
		for(int j = 0; j < n; ++j)
			if(!vis[j] && (t == -1 || dis[j] < dis[t]))
				t = j;
		vis[t] = 1;
		for(int j = 0; j < n; ++j){
    
			if(dis[j] > dis[t] + map[t][j]){
    
				dis[j] = dis[t] + map[t][j];
				sum[j] = sum[t] + a[t][j];
				path[j] = t;
			}
			else if(dis[j] == dis[t] + map[t][j]){
    
				if(sum[j] > sum[t] + a[t][j]){
    
					sum[j] = sum[t] + a[t][j];
					path[j] = t;
				}
			}
		}
	}
}
void dfs(int x){
    
	if(x == S){
    
		printf("%d", x);
		return;
	}
	dfs(path[x]);
	printf(" %d", x);
}
int main() {
    
	cin >> n >> m >> S >> D;
	memset(map, inf, sizeof map);
	for(int i = 0; i < n; ++i)
		map[i][i] = 0;
	while(m--){
    
		int x, y, z1, z2;
		cin >> x >> y >> z1 >> z2;
		map[x][y] = map[y][x] = z1;
		a[x][y] = a[y][x] = z2;
	}
	dijkstra(S);
	dfs(D);
	printf(" %d %d", dis[D], sum[D]);
}