UVA 10917 Walk Through the Forest ( Dijkstra + DP )

UVa Online Judge
用 Dijkstra 求一次從家裡到各個點的單源最短路徑，則所求是公司到家的路徑數，可走的有向邊只存在於滿足 DIjkstra 求出的 dis[ v ] < dis[ u ] 時的 u -> v，很明顯是個 DAG，用 DP 隨便處理就行了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e3 + 3;
const int INF = 1e9;

int n, m;
vector<pii> G[MAXN];

int vis[MAXN];
void dijkstra(int s, int *d){
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push( pii( 0, s ) );
    fill( d, d + MAXN, INF );
    d[s] = 0;
    fill( vis, vis + MAXN, 0 );
    while( !pq.empty() ){
        int u = pq.top().second; pq.pop();
        if( vis[ u ] ) continue;
        vis[ u ] = 1;
        for(pii z: G[ u ]){
            int c = z.first, v = z.second;
            if( d[ v ] > d[ u ] + c ){
                d[ v ] = d[ u ] + c;
                pq.push( pii( d[ v ], v ) );
            }
        }
    }
}

int dis[MAXN];
int way[MAXN];
int dp(int u){
    int &ans = way[u];
    if( ans != -1 ) return ans;
    if( u == 2 ) return ans = 1;
    ans = 0;
    for(int i = 0; i < G[u].size(); ++i){
        int v = G[u][i].second;
        if( dis[ v ] < dis[ u ] )
            ans += dp( v ); // transferable
    }
    return ans;
}

void solve(){
    dijkstra( 2, dis );
    memset( way, -1, sizeof(way) );
    printf("%d\n", dp( 1 ));
}

void init(){
    for(int i = 1; i <= n; ++i)
        G[i].clear();
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 ){
        init();
        for(int i = 0; i < m; ++i){
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            G[ a ].push_back( pii( c, b ) );
            G[ b ].push_back( pii( c, a ) );
        }
        solve();
    }
    return 0;
}