道路和航线

本质就是一个最短路，有负边，题目保证无环

直接跑的正确性就不用证明了

这道题卡掉了朴素的，用双端队列优化即可？

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int T, P, R, S, cur, dis[maxn];
int hed[maxn], edg[maxn], nxt[maxn], cst[maxn];

inline void AddEdge(int u, int v, int w)
{
    nxt[++cur] = hed[u];
    hed[u] = cur;
    edg[cur] = v;
    cst[cur] = w;
}

bool vis[maxn];

inline void SPFA()
{
    deque <int> Q;
    Q.push_front(S);
    dis[S] = 0;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop_front();
        vis[now] = 0;
        for (int i = hed[now]; i; i = nxt[i]) {
            if (dis[edg[i]] <= cst[i] + dis[now]) continue;
            dis[edg[i]] = cst[i] + dis[now];
            if (vis[edg[i]]) continue;
            vis[edg[i]] = 1;
            if (Q.empty() || dis[edg[i]] <= dis[Q.front()]) Q.push_front(edg[i]);
            else Q.push_back(edg[i]);
        }
    }
}

int main()
{
    T = __read(), R = __read(), P = __read(), S = __read();
    while (R--) {
        int a = __read(), b = __read(), c = __read();
        AddEdge(a, b, c), AddEdge(b, a, c);
    }
    while (P--) {
        int a = __read(), b = __read(), c = __read();
        AddEdge(a, b, c);
    }
    memset (dis, 0x3f, sizeof dis);
    SPFA();
    for (int i = 1; i <= T; ++i) {
        if (dis[i] == inf) puts("NO PATH");
        else printf ("%d\n", dis[i]);
    }
    system("pause");
}