道路与航线

题目描述：

n个点，R条双向边，P条单向边，双向边的权值都是正的，单向边的权值有正有负，给你一个起点，问起点到每个点的最短路是多少

思路1：

第一眼就看出来是SPFA板子题，但是敲上去发现SPFA被卡死了，但是用SLF优化一下SPFA就过了

思想是：将队列换成双端队列，塞点的时候先和队首比较一下，如果dis小于队首的dis，就把他塞到队首，否则塞到队尾

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m1, m2;
int s;
int a, b, c;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int dis[MAX];
bool vis[MAX];
void SPFA(){
    deque<int>q;q.push_back(s);vis[s] = 1;
    mem(dis, inf);dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop_front();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){
                    vis[v] = 1;
                    if(q.empty() || dis[v] > dis[q.front()])q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        if(dis[i] == inf)cout << "NO PATH\n";
        else cout << dis[i] << endl;
    }
}

void work(){
    cin >> n >> m1 >> m2 >> s;
    for(int i = 1; i <= m1; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    for(int i = 1; i <= m2; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}

思路2:

如果SPFA怎么优化都过不去的话怎么办？

题面最有意思的一个点是双向边的都是正权值，单向边的都是负权值，而我们不用迪杰斯特拉的原因是它不能跑负权值，那我们可以先将双向边的那些点进行缩点操作，因为是双向边，所以肯定会将原图变成一个个强连通分量，把每个强连通分量看成一个新点，这是图论中连通性问题常见的用法。再输入那P条单向边，现在就变成了一个有向无环图，我们一边拓扑排序一边迪杰斯特拉，连有向边的时候用一个数组计算每个强连通分量的入度，将入度为0的点塞进一个队列中，然后对队列内的点挨个跑迪杰斯特拉，迪杰斯特拉塞点之前先判断一下v和u是不是在一个连通块内，如果是才可以塞进去。如果v和 u不在一个连通块内，记得更新v所在的连通块的入度，入度为0时要及时入队

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m1, m2, s;
int a, b, c;

int num;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++num].to = v;
    tr[num].val = c;
    tr[num].nex = head[u];
    head[u] = num;
}



vector<int>v[MAX];
int tot;
int id[MAX];
void dfs(int u){
    id[u] = tot;
    v[tot].push_back(u);
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!id[v])dfs(v);
    }
    return;
}
queue<int>qq;
int du[MAX];
int dis[MAX];
bool vis[MAX];
void dijkstra(int p){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    for(auto x : v[p])q.push(m_p(dis[x], x));
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(id[v] == p)q.push(m_p(dis[v], v));
            }
            if(id[v] != p){
                --du[id[v]];
                if(!du[id[v]])qq.push(id[v]);
            }
        }
    }
}

void work(){
    cin >> n >> m1 >> m2 >> s;
    for(int i = 1; i <= m1; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    for(int i = 1; i <= n; ++i){
        if(!id[i]){
            ++tot;
            dfs(i);
        }
    }
    for(int i = 1; i <= m2; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
        ++du[id[b]];
    }
    for(int i = 1; i <= tot; ++i){
        if(!du[i])qq.push(i);
    }
    mem(dis, inf);
    dis[s] = 0;
    while (!qq.empty()) {
        dijkstra(qq.front());qq.pop();
    }
    for(int i = 1; i <= n; ++i){
        if(dis[i] > inf / 2)cout << "NO PATH\n";
        else cout << dis[i] << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

思路：根据题意我们可以吧双向的道路变成团，用航道连接不同的团形成一个DAG图，然后我们按拓扑排序去跑每个团里的迪杰斯特拉。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=1e9+7;
const int N=2e5+5;
const int inf=0x7f7f7f7f;

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
 
ll lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}
 
template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-')
            op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op)
        x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0)
        x = -x, putchar('-');
    if(x >= 10)
         write(x / 10);
    putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
    ll res=1%p;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return res;
}
struct node
{
    int to,nex,w;
}edge[N];
int tot,bcnt;
int n,tr,tp,s;
vector<int> block[N];
int head[N],id[N],din[N];
int dis[N],vis[N];
queue<int> q;
void add(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].nex=head[u];
    head[u]=tot++;
}

void dfs(int u,int bid)
{
    id[u]=bid;
    block[bid].push_back(u);
    for(int i=head[u];~i;i=edge[i].nex)
   {
       int v=edge[i].to;
        if(!id[v])dfs(v,bid);
   }

}
void dij(int x)
{
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    for(auto v:block[x])heap.push({dis[v],v});
    while(heap.size())
    {
        auto now=heap.top();heap.pop();
        int distance=now.first,ver=now.second;
        if(vis[ver])continue;
        vis[ver]=1;
        for(int i=head[ver];~i;i=edge[i].nex)
       {
           int v=edge[i].to,w=edge[i].w;
           if(dis[v]>dis[ver]+w)
           {
               dis[v]=dis[ver]+w;
               if(id[v]==id[ver])heap.push({dis[v],v});
           }
           if(id[v]!=id[ver]&&--din[id[v]]==0)q.push(id[v]);
       }

    }
}
void topusort()
{
    memset(dis,inf,sizeof dis);
    dis[s]=0;
    for(int i=1;i<=bcnt;i++)
    {
        if(!din[i])q.push(i);
    }
    while(q.size())
    {
        int t=q.front();q.pop();
        dij(t);
    }

}


int main()
{
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&tr,&tp,&s);
    while(tr--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }

    for(int i=1;i<=n;i++)
    {
        if(!id[i])dfs(i,++bcnt);
    }
    while(tp--)
    {
         int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        din[id[b]]++;
    }
    topusort();

    for(int i=1;i<=n;i++)
    {
        if(dis[i]>inf/2)puts("NO PATH");
        else printf("%d\n",dis[i]);
    }
   
   

   
   return 0;

}

思路：SPFA的优化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
const int mod=1e9+7;
const int M=(1<<10)+5;
const int inf=0x3f3f3f3f;
int n,T,R,S;
struct node
{
    int to,nex,w;
}edge[N];
int head[N],tot,dis[N],vis[N];
void add(int u,int v,int w)
{
    edge[++tot].to=v;
    edge[tot].w=w;
    edge[tot].nex=head[u];
    head[u]=tot;

}
void spfa()
{
    memset(dis,inf,sizeof dis);
    deque<int> q;
    dis[S]=0;
    q.push_back(S);
    vis[S]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(int i=head[x];~i;i=edge[i].nex)
        {
            int v=edge[i].to;
            if(dis[v]>dis[x]+edge[i].w){
                dis[v]=dis[x]+edge[i].w;
                if(!vis[v]){
                    vis[v]=1;
                if(q.empty()) q.push_back(v);
                else{
                    if(dis[v]<dis[q.front()])q.push_front(v);
                    else q.push_back(v);
                }
                }
            }
        }
    }

}
int main()
{
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&T,&R,&S);
    for(int i=0;i<T;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<R;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    spfa();
    for(int i=1;i<=n;i++)
    {
        if(dis[i]!=inf){
            printf("%d\n",dis[i]);
        }
        else{
            printf("NO PATH\n");
        }
    }
    return 0;


}