很明顯一看，這是多源最短路徑問題，看完y總視頻才知道，多源最短路徑比單源最短路徑簡單不少，
根據y總所說，多源最短路徑的基本思路是dp，怎么dp的呢，首先，
我們先設一個陣列d[k,i,j]，這代表什么呢，首先k是指經過前k個點，從i-j的最短距離，然后我們開始dp
d[k,i,j]=min(d[k-1,i,j],d[i][k]+d[k][j])
這是最核心的式子，經過第k個點的距離，與之前的遍歷結果進行比較不斷更新距離值，最后輸出d[n][i][j]即可，
然后我們其實可以寫成二維的式子，這樣大大減少了空間復雜度，
于是代碼如下，
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=210,Inf=1e9;
int g[N][N];
int n,m,k;
int main(void)
{
scanf("%d%d%d",&n,&m,&k);
for(int j=1;j<=n;j++)//在初始化g[i][j]的操作的時候我剛開始用memeset，發現好像不是很好用，然后要
//是賦值0x3f3f3f3f太大了，會溢位，
for(int i=1;i<=n;i++)
if(i==j)
g[i][j]=0;//需要注意自己到自己為0
else
g[i][j]=Inf;
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);//會出現重邊的情況，所以要取最小值，我們用的是鄰接矩陣，所以我們要更新操作
//好像鄰接表不用取更新，在后續的操作會自動把大的值忽略掉，
}
for(int p=1;p<=n;p++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
g[i][j]=min(g[i][j],g[i][p]+g[p][j]);
}
for(int i=1;i<=k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(g[a][b]>Inf/2)
printf("impossible\n");
else
printf("%d\n",g[a][b]);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261467.html
標籤：其他
上一篇：什么是MVP？
下一篇：pta基礎編程題目集7-26