#include <iostream> #include <sstream> #include <stdio.h> #include <string> #include <math.h> #include <algorithm> #include <stdlib.h> #include <stack> #include <map> #include <set> #include <queue> using namespace std; const int INF=1<<30; int n,m,k; int d[100]; int G[100][100]; bool vis[100]; void Dijkstra(int st) { fill(vis,vis+100,0); fill(d,d+100,INF); d[st]=0; for(int i=0;i<=n;i++) { int u=-1,MIN=INF; for(int j=0;j<=n;j++) if(vis[j]==0&&d[j]<MIN) { u=j; MIN=d[j]; } if(u==-1) return; vis[u]=1; for(int v=0;v<=n;v++) { if(vis[v]==0&&G[u][v]!=INF) { if(G[u][v]+d[u]<d[v]) d[v]=d[u]+G[u][v]; } } } } int main() { #ifdef ONLINE_JUDGE #else freopen("1.txt","r",stdin); #endif cin>>n>>m>>k; fill(G[0],G[0]+100*100,INF); while(m--) { int a,b,c; cin>>a>>b>>c; G[a][b]=G[b][a]=c; } while(k--) { int a,b; cin>>a>>b; Dijkstra(a); cout<<d[b]; if(k>0) cout<<endl; } return 0; } |
Double click to view unformatted code.