P3008 [usaco11jan]roads and planes g (SPFA + SLF optimization)

The title is as follows ：

[USACO11JAN]Roads and Planes G

Topic translation

Question description

Farmer John He is investigating his milk sales plan in a new sales area . He wants to deliver the milk $T$ A town ( $1\le T\le 25,000$ ), The number is $1$ To $T$ . Between these towns $R$ road ( $1\le R\le 50,000$ , The number is $1$ To $R$ ) and $P$ Routes ( $1\le P\le 50,000$ , The number is $1$ To $P$ ) Connect . Each road $i$ Or route $i$ Connecting towns $A_i$ ( $1\le A_i\le T$ ) To $B_i$ ( $1\le B_i\le T$ ), Cost is $C_i$ .

For roads $0\le C_i\le 10,000$ ; However, the cost of the route is amazing , cost $C_i$ It could be a negative number ( $-10,000\le C_i\le 10,000$ ). The road is two-way , It can be downloaded from $A_i$ To $B_i$, You can also get it from $B_i$ To $A_i$ , The cost is $C_i$ . However, the route is different , Only from $A_i$ To $B_i$ .

in fact , Because of the recent arrogance of terrorism , For social harmony , a Some policy guarantees ： If there is a route from $A_i$ To $B_i$, So it's impossible to get from China through some roads and routes $B_i$ go back to $A_i$ . because $FJ$ Our cows are recognized as awesome in the world , He needs to transport cows to every town . He wants to find the town from the sending center $S$ ( $1\le S\le T$) The cheapest way to send cows to every town , Or know that this is impossible .

Input format

common $R+P+1$ That's ok

The first $1$ That's ok ： Four integers $T$ , $R$ , $P$ and $S$ , Respectively represents the number of towns , Number of roads , Number of routes and central towns .

The first $2$ To $R+1$ That's ok ： Three integers per row $A_i$ , $B_i$ and $C_i$ , Describe a road .

The first $R+2$ To $R+P+1$ That's ok ： Three integers per row $A_i$ , $B_i$ and $C_i$ , Describe a route .

Output format

common $T$ That's ok , The first $i$ Row output City $S$ To the city $i$ Minimum cost of . If you can't get to , Output NO PATH

Title Description

Farmer John is conducting research for a new milk contract in a new territory. He intends to distribute milk to T (1 <= T <= 25,000) towns conveniently numbered 1…T which are connected by up to R (1 <= R <= 50,000) roads conveniently numbered 1…R and/or P (1 <= P <= 50,000) airplane flights conveniently numbered 1…P.

Either road i or plane i connects town A_i (1 <= A_i <= T) to town B_i (1 <= B_i <= T) with traversal cost C_i. For roads, 0 <= C_i <= 10,000; however, due to the strange finances of the airlines, the cost for planes can be quite negative (-10,000 <= C_i <= 10,000).

Roads are bidirectional and can be traversed from A_i to B_i or B_i to A_i for the same cost; the cost of a road must be non-negative.

Planes, however, can only be used in the direction from A_i to B_i specified in the input. In fact, if there is a plane from A_i to B_i it is guaranteed that there is no way to return from B_i to A_i with any sequence of roads and planes due to recent antiterror regulation.

Farmer John is known around the world as the source of the world’s finest dairy cows. He has in fact received orders for his cows from every single town. He therefore wants to find the cheapest price for delivery to each town from his distribution center in town S (1 <= S <= T) or to know that it is not possible if this is the case.

MEMORY LIMIT: 64MB

Input format

* Line 1: Four space separated integers: T, R, P, and S

* Lines 2…R+1: Three space separated integers describing a road: A_i, B_i and C_i

* Lines R+2…R+P+1: Three space separated integers describing a plane: A_i, B_i and C_i

Output format

* Lines 1…T: The minimum cost to get from town S to town i, or ‘NO PATH’ if this is not possible

Examples #1

The sample input #1

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10

Sample output #1

NO PATH 
NO PATH 
5 
0 
-95 
-100

Tips

6 towns. There are roads between town 1 and town 2, town 3 and town 4, and town 5 and town 6 with costs 5, 5 and 10; there are planes from town 3 to town 5, from town 4 to town 6, and from town 1 to town 3 with costs -100, - 100 and -10. FJ is based in town 4.

FJ’s cows begin at town 4, and can get to town 3 on the road. They can get to towns 5 and 6 using planes from towns 3 and 4. However, there is no way to get to towns 1 and 2, since they cannot go

backwards on the plane from 1 to 3.

Ideas ：

There is the shortest path with negative weight

SPFA + SLF You can get stuck ！

SPFA + SLF The board is as follows ：

void SPFA()
{
    
    deque<ll > q;
    d[s] = 0;
    q.push_back(s);
    vis[s] = 1;
    while(!q.empty())
    {
    
        ll x = q.front();
        q.pop_front();
        vis[x] = 0;
        for(int i=head[x]; i!=-1; i = nxt[i])
        {
    
            ll v = pnt[i];
            if(d[v] > d[x] + cost[i] )
            {
    
                d[v] = d[x] + cost[i] ;
                if(vis[v]) continue;
                vis[v] = 1;
                if(q.size()&&d[v]<d[q.front()])     //SLF, Small team leader , Big to the end of the team 
                q.push_front(v);
                else
                q.push_back(v);
            }
        }
    }
}

AC The code is as follows ：

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;

const int N = 1e6 + 9;
int n, m1, m2, gog;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool vis[N];
void add(int a, int b, int c)
{
    
    idx++;
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

void spfa(int goal)
{
    
    deque<int> q;
    for (int i = 1; i <= n; i++)
        dist[i] = 0x3f3f3f3f, vis[i] = 0;
    q.push_back(gog);
    dist[gog] = 0, vis[gog] = 1;
    while (!q.empty())
    {
    
        int t = q.front();
        q.pop_front();
        vis[t] = 0;

        for (int i = h[t]; i; i = ne[i])
        {
    
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
    
                dist[j] = dist[t] + w[i];
                if (vis[j])
                    continue;
                vis[j] = 1;
                if (q.size() && dist[j] < dist[q.front()])
                    q.push_front(j);
                else
                    q.push_back(j);
            }
        }
    }
}
void solve()
{
    
    cin >> n >> m1 >> m2 >> gog;

    int u, v, w;
    for (int i = 1; i <= m1; i++)
    {
    
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }

    for (int i = 1; i <= m2; i++)
    {
    
        cin >> u >> v >> w;
        add(u, v, w);
    }
    spfa(gog);
    for (int i = 1; i <= n; i++)
    {
    
        
        if (dist[i] == 0x3f3f3f3f)
            // puts("NO PATH");
            cout << "NO PATH" << '\n';
        else    
            cout << dist[i] << '\n';
    }
}
int main()
{
    
    buff;
    solve();
}