题意:图中有C个点,R条边,每个点有个权值,每条边也有距离值,求A到B点的最短距离＋经过的点的最大值的和最小
分析：比如说我们要求出S,T的“最短路”，我们可以枚举最大中间节点，因为这条路必经经过一个最大中间节点．
比如说我们找到点U的时候，就假设U是S到T路径上点权最大的点，可以把图上点权大于U的点去掉
然后d[ U,S ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”，每给出一个询问，查询即可。
// File Name: 10246.cpp // Author: Zlbing // Created Time: 2013/4/18 17:37:24 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=105; int C,R,Q; int P[MAXN]; struct Edge{ int u,v,cost; }; vector<Edge> edges; vector<int> G[MAXN]; struct node{ int u,cost; bool operator <(const node& rhs)const{ return cost>rhs.cost; } }; int V[MAXN][MAXN]; void dijkstra(int st) { priority_queue<node> Q; node t,tt; t.u=st; t.cost=0; Q.push(t); memset(V[st],-1,sizeof(V[st])); V[st][t.u]=0; while(!Q.empty()) { t=Q.top(); Q.pop(); for(int i=0;i<G[t.u].size();i++) { Edge e=edges[G[t.u][i]]; tt.u=e.v; tt.cost=t.cost+e.cost; if((V[st][e.v]==-1||V[st][e.v]>tt.cost)&&P[e.v]<=P[st]) { V[st][e.v]=tt.cost; Q.push(tt); } } } } int main() { int cas=0; //freopen("out.txt","w",stdout); while(~scanf("%d%d%d",&C,&R,&Q)) { if(C==0&&R==0&&Q==0) break; if(cas)printf("\n"); REP(i,1,C) { scanf("%d",&P[i]); } REP(i,1,C)G[i].clear(); edges.clear(); printf("Case #%d\n",++cas); REP(i,1,R) { int a,b,c; scanf("%d%d%d",&a,&b,&c); edges.push_back((Edge){a,b,c}); edges.push_back((Edge){b,a,c}); int m=edges.size(); G[a].push_back(m-2); G[b].push_back(m-1); } REP(i,1,C)dijkstra(i); REP(i,1,Q) { int a,b; scanf("%d%d",&a,&b); int ans=INF; REP(i,1,C) { if(V[i][a]==-1||V[i][b]==-1) continue; ans=min(ans,V[i][a]+V[i][b]+P[i]); } if(ans==INF)printf("-1\n"); else printf("%d\n",ans); } } return 0; }