Floyd
Floyd给人有一种dp的感觉。(但实际上最短路就是dp的一种?)
就很有背包的感觉这个算法,还是当把别的边当做踏板来到更近的边。
代码就是三重循环特别的暴力。。
代码
#include<cstdio>
using namespace std;
const int sz=201;
int d[sz][sz],n,m,t;
int min(int a,int b){return a<b?a:b;}
int main()
{
int i,j,k,x,y,z;
scanf("%d%d%d",&n,&m,&t);
for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(i!=j)d[i][j]=1e9;
for(i=1;i<=m;++i)scanf("%d%d%d",&x,&y,&z),d[x][y]=min(d[x][y],z);
for(k=1;k<=n;++k)for(i=1;i<=n;++i)for(j=1;j<=n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
while(t--)
{
scanf("%d%d",&x,&y);
if(d[x][y]>=9e8+9e7+9e6+9e5+9e4+9e3+9e2+20)printf("impossible\n");//一滴也加不进去了
else printf("%d\n",d[x][y]);
}
return 0;
}