100分代码,dijkstra

#include <bits/stdc++.h>
#define N (200000 + 10)  /*------------------ #define ------------------*/
#define M (2000000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
#define vvi vector<vector<int>>
#define vi vector<int>
#define vvl vector<vector<LL>>
#define vl vector<LL>
#define _vvi(n,m,k) vector<vector<int>>(n,vector<int>(m,k))
#define _vi(n,k) vector<int>(n,k)
#define _vvl(n,m,k) vector<vector<LL>>(n,vector<LL>(m,k))
#define _vl(n,k) vector<LL>(n,k)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,double> PDD;

int n,m;
int h[N],e[M],ne[M],w1[M],w2[M],idx;
int din[N],q[N];
bool isSource[N];
PII dist[N];
int pre[N];
bool st[N];
struct Node{
    int v,s,d;
    bool operator> (const Node &t) const {
        if(s != t.s) return s > t.s;
        return d < t.d;
    }
};

void add(int a,int b,int s,int d){
    e[idx] = b;
    w1[idx] = s,w2[idx] = d;
    ne[idx] = h[a],h[a] = idx ++ ;
}

int C = 0;

bool topsort(){
    int hh = 0,tt = -1;
    for(int i = 1;i <= n;i ++ )
        if(!din[i])
            q[++ tt] = i;
    while(hh <= tt){
        int t = q[hh ++];
        //cout << t << '\n';
        //if(++C >= 1000) return 0;
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(--din[j] == 0) q[++ tt] = j;
        }
    }
    return !(tt == n - 1);
}

void djikstra(){
    for(int i = 1;i <= n;i ++ )
        if(isSource[i])
            add(0,i,0,0);
    for(int i = 0;i <= n;i ++ )
        dist[i].fi = INF,dist[i].se = -INF;
    dist[0] = {0,0};
    priority_queue<Node,vector<Node>,greater<Node> > heap;
    heap.push((Node){0,dist[0].fi,dist[0].se});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.v;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver];~i;i = ne[i]){
            int j = e[i];
            if(dist[j].fi > dist[ver].fi + w1[i]){
                dist[j].fi = dist[ver].fi + w1[i];
                dist[j].se = dist[ver].se + w2[i];
                heap.push((Node){j,dist[j].fi,dist[j].se});
                pre[j] = ver;
            }else if(dist[j].fi == dist[ver].fi + w1[i] && dist[j].se < dist[ver].se + w2[i]){
                dist[j].se = dist[ver].se + w2[i];
                heap.push((Node){j,dist[j].fi,dist[j].se});
                pre[j] = ver;
            }
        }
    }
}

auto solve(){

    //djikstra();

    cin >> n >> m;
    memset(isSource,true,sizeof isSource);
    memset(h,-1,sizeof h);
    idx = 0;
    while(m -- ){
        int a,b,s,d;
        cin >> a >> b >> s >> d;
        a ++ ,b ++ ;
        add(a,b,s,d);
        din[b] ++ ;
        isSource[b] = false;
    }

    bool loop = false;
    loop = topsort();

    //cout << loop << '\n';

    int Q;
    cin >> Q;
    if(loop){
        cout << "Impossible.\n";
        while(Q -- ){
            int v;
            cin >> v;
            v ++ ;
            if(isSource[v]) cout << "You may take test " << (v - 1) << " directly.\n";
            else cout << "Error.\n";
        }   
    }else{
        cout << "Okay.\n";
        memset(pre,-1,sizeof pre);
        djikstra();
        while(Q -- ){
            int v;
            cin >> v;
            v ++ ;
            if(isSource[v]) cout << "You may take test " << (v - 1) << " directly.\n";
            else{
                int t = v;
                vector<int> res;
                while(t != -1){
                    res.push_back(t);
                    t = pre[t];
                }
                reverse(res.begin(),res.end());
                //cout << (res[0] - 1);
                cout << (res[1] - 1);
                for(int i = 2;i < (int)res.size();i ++ )
                    cout << "->" << (res[i] - 1);
                cout << '\n';
            }
        }
    }
}

signed main(){
    IOS
    int T = 1;
    //cin >> T;
    while(T -- ) solve();
    //while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';

    return 0;
}