乍看是带点权的最短路,实际上最短路再加上最大点权最小的时候才是最短,即min{ path(S,T) + min{w[i]|i on path from S to T}}.我表示没有思路,看的题解做的。。比如说我们要求出S,T的“最短路”,我们可以枚举最大中间节点,因为这条路必经经过一个最大中间节点,比如说我们找到点U的时候,就假设U是S到T路径上点权最大的点,可以把图上点权大于U的点去掉然后d[ S, U ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”,每给出一个询问,查询即可。
//变量名写错了,类里面的dijkstra我实际上用的是spfa。。。 #include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> const int INF = 2100000000; using namespace std; class Edge{ public: int to,w; Edge *next; void add( int tt, int ww, Edge *&b){ to=tt;w=ww;next=b;b=this; } }; template<int Vsize, int Esize> class ShortestPath{ public: int N,countt,d[ Vsize ]; Edge A[ Esize*10 ],*biao[ Vsize ]; public: ShortestPath() {} ShortestPath(int n) { init(n);} int operator [] (int i){ return d[i]; } void init( int n ){ N = n;countt = 0; for( int i = 0; i <= N; i++ ) biao[i] = NULL; } void add( int from, int to ,int w ){ A[ countt++ ].add( to, w, biao[from] ); } void Dijkstra( int S,int *wp ){ int now,i,minn,inq[Vsize]; queue<int> q; for( i = 0; i <= N; i++ ) d[i] = INF; memset( inq, 0, sizeof(inq) ); d[S] = 0; q.push( S ); while( !q.empty() ){ int u = q.front();q.pop(); inq[u] = 0; for(Edge *p = biao[u];p!=NULL;p=p->next) if( d[p->to] > d[u] + p->w && wp[p->to]<=wp[S] ){ d[p->to] = d[u] + p->w; if( !inq[p->to] ){ inq[p->to]= 1; q.push( p->to); } } } } }; int wp[ 100 ]; int map[ 100 ][ 100 ]; ShortestPath<100, 3000 > SP; int main(void){ int N,M,Q,i,j,k,cases=0; int from,to,w,minn; while( scanf("%d%d%d",&N,&M,&Q) != EOF ){ if( !N && !M && !Q ) break; SP.init(N); for( i = 1; i <= N ; i++ ) scanf("%d",&wp[i]); while( M-- ){ scanf("%d%d%d",&from,&to,&w); SP.add( from, to, w ); SP.add( to, from, w ); } for( i = 1; i <= N; i++ ){ SP.Dijkstra(i,wp); for( j = 1; j <= N; j++ ) map[i][j] = SP[j]; } if( cases ) printf("\n"); printf("Case #%d\n",++cases); while( Q-- ){ scanf("%d%d",&from,&to); minn = INF; for( i = 1; i <= N; i++ ){ if( map[i][from] == INF ) continue; if( map[i][to] == INF ) continue; minn = min( minn, map[i][from]+wp[i]+map[i][to] ); } if( minn == INF ) printf("-1\n"); else printf("%d\n",minn); } } return 0; }
为啥这里没有留言板呢?
求党姐的交换链接
如果N=1000?
模板参数可以改点个数。。。(?)