think: 1Dijkstra算法 2二維結(jié)構(gòu)體數(shù)組
sdut原題鏈接
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之圖論七：驢友計(jì)劃 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 做為一個(gè)資深驢友，小新有一張珍藏的自駕游線路圖，圖上詳細(xì)的標(biāo)注了全國(guó)各個(gè)城市之間的高速公路距離和公路收費(fèi)情況，現(xiàn)在請(qǐng)你編寫一個(gè)程序，找出一條出發(fā)地到目的地之間的最短路徑，如果有多條路徑最短，則輸出過路費(fèi)最少的一條路徑。
Input 連續(xù)T組數(shù)據(jù)輸入，每組輸入數(shù)據(jù)的第一行給出四個(gè)正整數(shù)N,M，s，d，其中N(2 <= N <= 500)是城市數(shù)目，城市編號(hào)從0～N-1，M是城市間高速公路的條數(shù)，s是出發(fā)地的城市編號(hào)，d是目的地的城市編號(hào)；隨后M行，每行給出一條高速公路的信息，表示城市1、城市2、高速公路長(zhǎng)度、收費(fèi)額，中間以空格間隔，數(shù)字均為整數(shù)且不超過500，輸入數(shù)據(jù)均保證有解。
Output 在同一行中輸出路徑長(zhǎng)度和收費(fèi)總額，數(shù)據(jù)間用空格間隔。
Example Input 1 4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20
Example Output
3 40
Hint
Author xam
以下為accepted代碼
#include <stdio.h>#include <string.h>#define INF 0x3f3f3f3fint n, m;int vis[504];struct node{ int data; int ans;}map[504][504], dist[104], min;void Dijkstra(int v){ int i, j, k; for(i = 0; i < n; i++) { dist[i] = map[v][i]; vis[i] = 0; } vis[v] = 1; dist[v].data = 0; dist[v].ans = 0; for(i = 0; i < n-1; i++) { int u = v; min.data = INF; min.ans = INF; for(j = 0; j < n; j++) { if(vis[j] == 0 && dist[j].data == min.data && dist[j].ans < min.ans) { u = j; min = dist[j]; } if(vis[j] == 0 && dist[j].data < min.data) { u = j; min = dist[j]; } } vis[u] = 1; for(k = 0; k < n; k++) { if(vis[k] == 0 && map[u][k].data < INF) { if(dist[k].data > dist[u].data + map[u][k].data) { dist[k].data = dist[u].data + map[u][k].data; dist[k].ans = dist[u].ans + map[u][k].ans; } if(dist[k].data == dist[u].data + map[u][k].data && dist[k].ans > dist[u].ans + map[u][k].ans) { dist[k].data = dist[u].data + map[u][k].data; dist[k].ans = dist[u].ans + map[u][k].ans; } } } }}int main(){ int T, s, t, i, j, u, v, x, y; scanf("%d", &T); while(T--) { scanf("%d %d %d %d", &n, &m, &s, &t); for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(i == j) { map[i][j].data = 0; map[i][j].ans = 0; } else { map[i][j].data = INF; map[i][j].ans = INF; } } } for(i = 0; i < m; i++) { scanf("%d %d %d %d", &u, &v, &x, &y); map[u][v].data = map[v][u].data = x; map[u][v].ans = map[v][u].ans = y; } Dijkstra(s); printf("%d %d/n", dist[t].data, dist[t].ans); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 128KBSubmit time: 2017-02-19 11:17:47****************************************************/新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
