幸好考前做了一遍y总的题
我之前自己整理的板子从来都没考虑
重!边!和!自!环!
结果这几个最短路的板子题我居然调了一下午
dij是可以自己自动处理重边的
但是floyd不星
其他的地方都很简单啦
//来自算法基础课
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 233;
const int M = 23333;
const int INF = 1e9;
int n,m,t;
int dist[N][N];
int main() {
read(n), read(m),read(t);
for(register int i=1; i<=n; i++)
for(register int j=1; j<=n; j++) {
if(i==j) dist[i][j]=0;
else dist[i][j] = INF;
}
for(register int i=1; i<=m; i++) {
int s,e,l;
read(s),read(e),read(l);
if(s==e) continue;//处理自环
dist[s][e] = min(dist[s][e],l);//处理重边
}
for(register int k=1; k<=n; k++)
for(register int i=1; i<=n; i++)
for(register int j=1; j<=n; j++)
dist[i][j] = min(dist[i][k]+dist[k][j],dist[i][j]);
while(t--) {
int x,y;
read(x),read(y);
if(dist[x][y]>INF/2) printf("impossible\n");
else printf("%d\n",dist[x][y]);
}
return 0;
}