#include<iostream> #include<iomanip> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<stack> #include<queue> #include<set> #include<map> #include<vector> #define ll long long using namespace std; const int inf=0x3f3f3f3f; int n,m,k; int e[1000][1000]; int dis[1000][1000]; void dij(int a) { int book[1000]={0}; for(int i = 1; i <= n; i++) dis[a][i] = e[a][i]; //初始化dis为源点到各点的距离 for(int i = 1; i <= n; i++) book[i] = 0; book[a] = 1; //初始时P集合中只有源点 for(int i = 1; i <= n-1; i++) //做n-1遍就能把Q遍历空 { int min = inf; int u; for(int j = 1; j <= n; j++) //寻找Q中最近的结点 { if(book[j] == 0 && dis[a][j] < min) { min = dis[a][j]; u = j; } } book[u] = 1; //加入到P集合 for(int v = 1; v <= n; v++) //对u的所有出边进行松弛 { if(e[u][v] < inf) { if(dis[a][v] > dis[a][u] + e[u][v]) dis[a][v] = dis[a][u] + e[u][v]; } } } } int main() { cin>>n>>m>>k; memset(e,inf,sizeof(e)); for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e[a][b]=c; } for(int i=0;i<n;i++) { e[i][i]=0; } for(int i=0;i<n;i++) { dij(i); } for(int i=0;i<k;i++) { int a,b; scanf("%d%d",&a,&b); printf("%d\n",dis[a][b]); } } |
Double click to view unformatted code.