【（图） 旅游规划 (25 分)】【Dijkstra算法】
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 500; const int INF = 0x3f3f3f3f; struct Road { int _len; int _cost; }road[maxn][maxn]; int vis[maxn]; struct City { int _len; int _cost; }d[maxn]; int N, M, S, D; void init() { for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) road[i][j]._len = INF, road[i][j]._cost = INF; for(int i = 0; i < N; i++) d[i]._len = INF, d[i]._cost = INF; d[S]._len = 0; d[S]._cost = 0; } void solve() { memset(vis, 0, sizeof(vis)); for(int i = 1; i <= N; i++) { int x, minlen = INF; for(int j = 0; j < N; j++) { if(!vis[j] && d[j]._len < minlen) { minlen = d[j]._len; x = j; } } vis[x] = 1; if(minlen == INF) break; for(int y = 0; y < N; y++) { if(!vis[y]) { if(d[y]._len > d[x]._len + road[x][y]._len) { d[y]._len = d[x]._len + road[x][y]._len; d[y]._cost = d[x]._cost + road[x][y]._cost; } else if(d[y]._len == d[x]._len + road[x][y]._len) d[y]._cost = min(d[y]._cost, d[x]._cost + road[x][y]._cost); } } } } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d %d %d %d", &N, &M, &S, &D); init(); int a, b, c, dd; for(int i = 0; i < M; i++) { scanf("%d %d %d %d", &a, &b, &c, &dd); road[a][b]._len = road[b][a]._len = c; road[a][b]._cost = road[b][a]._cost = dd; } solve(); printf("%d %dn", d[D]._len, d[D]._cost); }
