【每日一题】9月11日题目精讲

SPFA+SLF优化，直接朴素的SPFA会卡掉。
当然用SPFA+LLL+SLF应该也是可以的，但是我不是很会LLL，但是一个SLF优化就可以过了。
题目当中说：双向边是非负的而单向边没有环，所以，我们可以先把有双向边链接的若干个点缩成一个点，然后点之间连上单向边之后这张图是一个有向无环图，所以跑广搜就可以了。而连通块内部因为边非负，所以可以dijkstra。

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
///////////////////////////////////////////////////////////
int n,m,w;
int T, R, P, S;
struct Edge
{
    int v, w, next;
}edge[N];
int head[N], dis[N],  t;
bool vis[N];
void init(){
    memset(dis, 0x3f, sizeof dis);
}
inline void Add_edge(int u, int v, int w)
{
    edge[++t].next= head[u];
    head[u] = t;
    edge[t].v = v;
    edge[t].w = w;
}
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 = head[now]; i; i = edge[i].next) {
            if (dis[edge[i].v] <= edge[i].w + dis[now]) continue;
            dis[edge[i].v] = edge[i].w + dis[now];
            if (vis[edge[i].v]) continue;
            vis[edge[i].v] = 1;
            if (q.empty() || dis[edge[i].v] <= dis[q.front()]) q.push_front(edge[i].v);
            else q.push_back(edge[i].v);
        }
    }
}
int main()
{
    cin>>T>>R>>P>>S;
     while (R--) {
        int a,b,c;
        cin>>a>>b>>c;
        Add_edge(a, b, c), Add_edge(b, a, c);
    }
    while (P--) {
        int a,b,c;
        cin>>a>>b>>c;
        Add_edge(a, b, c);
    }
    init();
    SPFA();
    for (int i = 1; i <= T; ++i) {
        if (dis[i] == INF) {
            cout<<"NO PATH"<<endl;
        }
        else {
            cout<<dis[i]<<endl;
        }
    }
    return 0;
}