生活随笔
收集整理的這篇文章主要介紹了
数据结构实验之图论七：驴友计划(最短路Floyd/Dijkstra)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Description
做為一個資深驢友，小新有一張珍藏的自駕游線路圖，圖上詳細的標注了全國各個城市之間的高速公路距離和公路收費情況，現在請你編寫一個程序，找出一條出發地到目的地之間的最短路徑，如果有多條路徑最短，則輸出過路費最少的一條路徑。
Input
連續T組數據輸入，每組輸入數據的第一行給出四個正整數N,M，s，d，其中N(2 <= N <= 500)是城市數目，城市編號從0～N-1，M是城市間高速公路的條數，s是出發地的城市編號，d是目的地的城市編號；隨后M行，每行給出一條高速公路的信息，表示城市1、城市2、高速公路長度、收費額，中間以空格間隔，數字均為整數且不超過500，輸入數據均保證有解。
Output
在同一行中輸出路徑長度和收費總額，數據間用空格間隔。
Sample
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
Output
3 40
Hint
本文提供多個解析選擇適合自己的食用！
Floyd - Warshall（弗洛伊德算法、啊哈算法）
啊哈算法中的Dijkstra算法
ACM_最短路講解
#include<bits/stdc++.h>using namespace std
;#define INF 0x3f3f3f3f
const int N
= 555;int G
[N
][N
];
int P
[N
][N
];
void init(int n
)
{for(int i
= 0; i
< n
; i
++){for(int j
= 0; j
< n
; j
++){if(i
== j
)G
[i
][j
] = 0;elseG
[i
][j
] = INF
;}}
}
void Floyd(int n
, int s
, int d
)
{for(int k
= 0; k
< n
; k
++){for(int i
= 0; i
< n
; i
++){for(int j
= 0; j
< n
; j
++){if(G
[i
][j
] > G
[i
][k
] + G
[k
][j
]){G
[i
][j
] = G
[i
][k
] + G
[k
][j
];P
[i
][j
] = P
[i
][k
] + P
[k
][j
];}else if(G
[i
][j
] == G
[i
][k
] + G
[k
][j
]){P
[i
][j
] = min(P
[i
][j
], P
[i
][k
] + P
[k
][j
]);}}}}cout
<< G
[s
][d
] << ' ' << P
[s
][d
] << endl
;
}
int main()
{int t
;cin
>> t
;while(t
--){int n
, m
, s
, d
;cin
>> n
>> m
>> s
>> d
;init(n
);while(m
--){int u
, v
, len
, value
;cin
>> u
>> v
>> len
>> value
;G
[u
][v
] = G
[v
][u
] = len
;P
[u
][v
] = P
[v
][u
] = value
;}Floyd(n
, s
, d
);}return 0;
}
#include<bits/stdc++.h>using namespace std
;#define INF 0x3f3f3f3fconst int N
= 550;
int mp
[N
][N
];
int book
[N
];
int money
[N
][N
];int dist
[N
];
int mon
[N
];void Dijkstra(int n
, int s
, int d
)
{int i
, j
, v
, minn
, u
= 0;for(i
= 0; i
< n
; i
++){dist
[i
] = mp
[s
][i
];mon
[i
] = money
[s
][i
];}dist
[s
] = 0;book
[s
] = 1;mon
[s
] = 0;for(i
= 1; i
< n
; i
++){minn
= INF
;for(j
= 0; j
< n
; j
++){if(minn
> dist
[j
] && !book
[j
]){minn
= dist
[j
];u
= j
;}}book
[u
] = 1;for(v
= 0; v
< n
; v
++){if(mp
[u
][v
] < INF
&& ! book
[v
]){if(dist
[v
] > dist
[u
] + mp
[u
][v
]){dist
[v
] = dist
[u
] + mp
[u
][v
];mon
[v
] = mon
[u
] + money
[u
][v
];}else if(dist
[v
] == dist
[u
] + mp
[u
][v
]){if(mon
[v
] > mon
[u
] + money
[u
][v
]){mon
[v
] = mon
[u
] + money
[u
][v
];}}}}}cout
<< dist
[d
] << ' ' << mon
[d
] << endl
;
}int main()
{int t
, u
, v
, n
, m
, s
, d
, len
, cost
;scanf("%d", &t
);while(t
--){scanf("%d %d %d %d",&n
,& m
, &s
, &d
);memset(book
, 0, sizeof(book
));memset(mp
, INF
, sizeof(mp
));for(int i
= 0; i
< n
;i
++){mp
[i
][i
] = 0;}while(m
--){scanf("%d %d %d %d",&u
, &v
, &len
, &cost
);mp
[u
][v
] = mp
[v
][u
] = len
;money
[u
][v
] = money
[v
][u
] = cost
;}Dijkstra(n
, s
, d
);}return 0;
}
總結
以上是生活随笔為你收集整理的数据结构实验之图论七：驴友计划(最短路Floyd/Dijkstra)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
