題目
給定一個(gè)n個(gè)點(diǎn)m條邊的有向圖，圖中可能存在重邊和自環(huán)，邊權(quán)可能為負(fù)數(shù)。
再給定k個(gè)詢問，每個(gè)詢問包含兩個(gè)整數(shù)x和y，表示查詢從點(diǎn)x到點(diǎn)y的最短距離，如果路徑不存在，則輸"impossible”。
數(shù)據(jù)保證圖中不存在負(fù)權(quán)回路。
輸入格式
第一行包含三個(gè)整數(shù)n, m, k
接下來m行，每行包含三個(gè)整數(shù)x, y，z，表示點(diǎn)x和點(diǎn)y之間存在一條有向邊，邊長為z。接下來k行，每行包含兩個(gè)整數(shù)x，y，表示詢問點(diǎn)x到點(diǎn)y的最短距離。
輸出格式
共k行，每行輸出一個(gè)整數(shù)，表示詢問的結(jié)果，若詢問兩點(diǎn)間不存在路徑，則輸出"impossible”。
數(shù)據(jù)范圍
1≤n ≤200,1 ≤k≤n2
1 ≤m ≤20000,
圖中涉及邊長絕對(duì)值均不超過10000。
- 輸入樣例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
- 輸出樣例:
impossible
1
題解
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210，INF = 1e9;
int n, m,Q;
int d[N][N];
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i + )
for (int j = 1; j <= n; j ++ )
d[i][j]= min(d[i][j]，d[i][k] +d[k][j]);
}
int main()
{
scanf("%d%d%d"，&n，&m，&Q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j]=0;else d[i][j] = INF;
while (m -- )
{
int a, b, w;
scanf("%d%d%d"，&a，&b，&w);
d[a][b] = min(d[a][b], w);
}
floyd( );
while (Q -- )
{
int a, b;
scanf("%d%d"，&a，&b);
if (d[a][b] >INF / 2) puts("impossible")
else printf("%d", d[a][b]);
}
return 0;
}
題解
Floyd是一個(gè)簡單的處理多源最短路徑的方法，時(shí)間復(fù)雜度為O（n3）
Floyd模板就是文章來源：http://www.zghlxwxcb.cn/news/detail-534254.html
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i + )
for (int j = 1; j <= n; j ++ )
d[i][j]= min(d[i][j]，d[i][k] +d[k][j]);
}
帶入模板即可解決問題，具體原理可以自行搜索博客，也很簡單，在這里就不想詳述了。文章來源地址http://www.zghlxwxcb.cn/news/detail-534254.html
到了這里，關(guān)于Acwing.854 Floyd求最短路 (Floyd算法)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
