HDU 2680

HDU - 2680

SPFA + 反向建图

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e3 + 10,M = 4e4 + 10,INF = 0x3f3f3f3f;
int e[M],ne[M],h[N],w[M],idx,dist[N],n,m,s;
bool st[N];
void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void spfa(){
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    st[s] = 1;
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = 0;
        for(int j = h[t];j != -1;j = ne[j]){
            int x = e[j];
            if(dist[x] > dist[t] + w[j]){
                dist[x] = dist[t] + w[j];
                if(!st[x]){
                    q.push(x);
                    st[x] = 1;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int x,y,z;
    while(cin >> n >> m >> s){
        idx = 0;
        memset(dist,0x3f,sizeof dist);
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        while(m--){
            cin >> x >> y >> z;
            add(y,x,z);
        }
        spfa();
        cin >> x;
        int ans = INF;
        while(x--){
            cin >> y;
            ans = min(ans,dist[y]);
        }
        if(ans != INF) cout << ans;
        else cout << "-1";
        cout << endl;
    }
    return 0;
}

朴素Dij + 缩点(cin 关了同步流也TLE)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e3 + 10,M = 4e4 + 10,INF = 0x3f3f3f3f;
int g[N][N],dist[N],n,m,s;
bool st[N];
void dij(){
    dist[0] = 0;
    for(int i = 0;i < n; ++i){
        int t = -1;
        for(int j = 0;j <= n; ++j){
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = 1;
        for(int j = 0;j <= n; ++j){
            if(dist[j] > dist[t] + g[t][j]){
                dist[j] = dist[t] + g[t][j];

            }
        }
    }
}
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    int x,y,z;
    while(scanf("%d%d%d",&n,&m,&s) != EOF){
        memset(dist,0x3f,sizeof dist);
        memset(st,0,sizeof st);
        for(int i = 0;i <= n; ++i)
            for(int j = 0;j <= n; ++j)
                if(i == j) g[i][j] = 0;
                else g[i][j] = INF;
        while(m--){
            scanf("%d%d%d",&x,&y,&z);
            g[x][y] = min(g[x][y],z);
        }
        scanf("%d",&x);
        while(x--){
            scanf("%d",&y);
            g[0][y] = 0;
        }
        dij();
        if(dist[s] != INF) printf("%d",dist[s]);
        else printf("-1");
        puts("");
    }
    return 0;
}