道路和航线题解

题目：道路和航线
题：https://ac.nowcoder.com/acm/problem/50381
题意：给定有向边（可负权边），无向边（不可负权边），问从S点到任意一点的最短路边权，若不能到达则输出“NO PATH”
分析：负权边不可用dijkstra最短路来求，只能依靠spfa来求，其中queue版本会超时，所以采用deque版本来优化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
using namespace std;
typedef long long ll;
#define MP make_pair
#define pii pair<int,int>
#define pb push_back
const int inf=0x3f3f3f3f;
const int M=2e5+5;
vector< pii >g[M];
int dis[M],vis[M];
void SPFA(int s,int n){
    for(int i=0;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    deque<int>que;
    que.push_front(s);
    while(!que.empty()){
        int u=que.front();
        que.pop_front();
        vis[u]=0;
        for(auto it:g[u]){
            int v=it.first,w=it.second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    if(que.empty()||dis[v]<=dis[que.front()])
                        que.push_front(v);
                    else
                        que.push_back(v);
                }
            }
        }
    }
}
int main(){
    int T,R,P,S;
    scanf("%d%d%d%d",&T,&R,&P,&S);
    for(int u,v,w,i=1;i<=R;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb(MP(v,w));
        g[v].pb(MP(u,w));
    }
    for(int u,v,w,i=1;i<=P;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb(MP(v,w));
    }
    SPFA(S,T);
    for(int i=1;i<=T;i++){
        if(dis[i]==inf)
            puts("NO PATH");
        else
            printf("%d\n",dis[i]);
    }
    return 0;
}