UVA 10246 Asterix and Obelix (最短路变形)

UVA 10246 Asterix and Obelix

乍看是带点权的最短路，实际上最短路再加上最大点权最小的时候才是最短，即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;
}