POJ-3159: Candies

keyword

Dijkstra　C++

問題概要

ノード数V(<3*10^4)、辺の数E(<1.5*10^5)の重み付き有向グラフが与えられる。ある点からある点までの距離を求める問題。

解法

DijkstraするだけなんだけどTLEが異常に厳しいので細々とした高速化をして通った。Forum見てるとSPFAという方法があるらしく、ちょっと調べてみたけどBellman-Fordとの違いがよく分からなかった。priority_queueを使っていない分早くなるかもしれないということなんだろうか。

#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

inline int readint(){
    int ret = 0, x;
    bool plus = true;
    while(x=getchar(), !('0'<=x&&x<='9' || x=='-'));
    if(x=='-') plus = false;
    else ret = (x&15);
    while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);
    return plus?ret:-ret;
}

typedef long long int64;

const int MAX_N = 30002;
const int64 MASK = 0xffff;
int N, M;
bool visited[MAX_N];
vector<int64> G[MAX_N];

int dijkstra(int from, int to){
    memset(visited, 0, sizeof(visited));
    priority_queue<int64, vector<int64>, greater<int64> > Q;
    Q.push( from );
    while(!Q.empty()){
        int64 tp = Q.top(); Q.pop();
        int v = tp&MASK;
        int64 d = (tp>>16);
        if(v == to) return d;
        if(visited[v]) continue;
        visited[v] = true;
        for(int i=0; i<G[v].size(); i++){
            int u = G[v][i]&MASK;
            if(!visited[u]){
                Q.push( ((d + (G[v][i]>>16))<<16) + u ) ;
            }
        }
    }
    return 0x7fffffff;
}

int solve(){
    return dijkstra(0,N-1);
    //return max(dijkstra(0,N-1), dijkstra(N-1,0));
}

int main(){
    N = readint(); M = readint();
    for(int i=0; i<M; i++){
        int a=readint(), b=readint();
        int64 c=readint();
        G[a-1].push_back( (c<<16)+b-1 );
    }
    printf("%d\n",solve());
    return 0;
}