题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=28972
思路：spfa求出每个点到其余顶点的最短路（最短路上的每个点的val都小于等于起点的val），然后又二维数组dp来保存，最后询问的时候就是枚举中间点i了，min{dp[i][u]+dp[i][v]+cost[i]};
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 #define inf 1<<30 9 10 struct Edge{ 11 int v,w; 12 Edge(){} 13 Edge(int vv,int ww):v(vv),w(ww){} 14 }; 15 16 vector<vector<Edge> >g; 17 int cost[111],dist[111],dp[111][111]; 18 bool mark[111]; 19 int n,m,Q; 20 21 void spfa(int s) 22 { 23 memset(mark,false,sizeof(mark)); 24 fill(dist,dist+n+1,inf); 25 dist[s]=0; 26 queue<int>que; 27 que.push(s); 28 while(!que.empty()){ 29 int u=que.front(); 30 que.pop(); 31 mark[u]=false; 32 for(int i=0;i<g[u].size();i++){ 33 int v=g[u][i].v,w=g[u][i].w; 34 if(dist[u]+w<dist[v]&&cost[v]<=cost[s]){ 35 dist[v]=dist[u]+w; 36 if(!mark[v]){ 37 mark[v]=true; 38 que.push(v); 39 } 40 } 41 } 42 } 43 for(int i=1;i<=n;i++)dp[s][i]=dist[i]; 44 } 45 46 47 int main() 48 { 49 int u,v,w,t=0; 50 while(~scanf("%d%d%d",&n,&m,&Q)){ 51 if(n==0&&m==0&&Q==0)break; 52 for(int i=1;i<=n;i++)scanf("%d",&cost[i]); 53 g.clear(); 54 g.resize(n+2); 55 while(m--){ 56 scanf("%d%d%d",&u,&v,&w); 57 g[u].push_back(Edge(v,w)); 58 g[v].push_back(Edge(u,w)); 59 } 60 for(int i=1;i<=n;i++) 61 for(int j=1;j<=n;j++)dp[i][j]=inf; 62 for(int i=1;i<=n;i++)spfa(i); 63 if(t)puts(""); 64 printf("Case #%d\n",++t); 65 while(Q--){ 66 scanf("%d%d",&u,&v); 67 int ans=inf; 68 for(int i=1;i<=n;i++){ 69 if(dp[i][u]==inf||dp[i][v]==inf)continue; 70 ans=min(ans,dp[i][u]+dp[i][v]+cost[i]); 71 } 72 if(ans==inf)ans=-1; 73 printf("%d\n",ans); 74 } 75 } 76 return 0; 77 } 78 79