牛客小白月赛24 E—旅游旅游 (Dijkstra||spfa+并查集)

整理的算法模板：ACM算法模板总结（分类详细版）

链接：https://ac.nowcoder.com/acm/contest/5158/E
来源：牛客网
 

题目描述

牛牛国有 nnn 个城市，mmm 条无向道路，每条道路三个属性 ai,bi,cia_i,b_i,c_iai​,bi​,ci​，表示城市 aia_iai​ 与城市 bib_ibi​ 之间有一条长为 cic_ici​ 的道路，现在牛可乐在城市 111，他想去城市 nnn。同时牛可乐非常聪明，他会将所有从1到 nnn 可能的最短路径全都走一遍，之后便不再走了。

现在牛妹在城市 111，他想把所有城市走一遍，可是他不想走牛可乐走过的路，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？

输入描述:

第一行两个数字 n,mn,mn,m，表示城市的数量和道路的数量。

接下来 mmm 行，每行 333 个数字 ai,bi,cia_i,b_i,c_iai​,bi​,ci​，表示城市 aia_iai​ 与城市 bib_ibi​ 之间有一条长为 cic_ici​ 的道路  (题目保证无自环，可能有重边)

 

输出描述:

如果牛妹能走遍所有城市，输出 “YES” ，否则输出 “NO”。

示例1

输入

复制4 5 1 2 2 1 3 2 2 3 1 2 4 2 3 4 1

4 5
1 2 2
1 3 2
2 3 1
2 4 2
3 4 1

输出

复制YES

YES

说明

城市1到城市4最短路距离是3(1->3->4)，牛妹不能走这些边也能走遍所有城市。

备注:

1≤n≤1e5,1≤m≤5e51\leq n\leq 1e5,1\leq m\leq 5e51≤n≤1e5,1≤m≤5e5

1≤ai,bi≤n,1≤ci≤1e91\leq a_i,b_i\leq n,1\leq c_i\leq 1e91≤ai​,bi​≤n,1≤ci​≤1e9

建议使用 scanf 读入

 

思路很简单：（Dijkstra换成spfa算法也可，不过时间复杂度没y总说的那么优化，还是Dijkstra好点）

• 从1到n做一次dijkstra，求出1到每个点的最短距离dist1
• 从n到1再做一次dijkstra，求出从n到每个点的最短距离dist2，
• 如果有一条边u—>v 的长度len ,满足 dist1[u]+ len + dist2[v] ==min_dis（min_dis为1~n的最短距离）则说明这条边不在最短路径上面，可以把他们用并查集放在一个集合里面，判断完所有的边之后，查找是否所有的点都在一个集合里面即可；

一道简单的图论活生生给我做废了，注意两点：数组的初始化，最大值的设定（爆longlong）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7,M=1e6+7;
typedef long long ll;
typedef pair<ll,ll> PII;
ll e[M],ne[M],w[M],h[M],idx,pre[N];
ll dist[2][N],n,m;
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra(int root)
{
    int k=root%n;
    for(int i=0;i<=n;i++) dist[k][i]=0x3f3f3f3f3f3f3f3f,st[i]=false;
    dist[k][root] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, root});      // first存储距离，second存储节点编号
    
    while (heap.size())
    {
        
        auto t = heap.top();
        heap.pop();
        ll ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[k][j] > distance + w[i])
            {
                dist[k][j] = distance + w[i];
                heap.push({dist[k][j], j});
            }
        }
    }
}
int find(int x)
{
    if(pre[x]!=x)
    {
        pre[x]=find(pre[x]);
    }
    return pre[x];
}
int main()
{
    queue<PII> ww;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n;i++) h[i]=-1,pre[i]=i;
    for(int i=0;i<m;i++)
    {
        ll a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
        ww.push({a,b});
        
    }
    dijkstra(1);
    dijkstra(n);
    ll min_dis=dist[1][n];
    int cnt=0;
    while(!ww.empty())
    {
        auto res=ww.front();
        ww.pop();
        ll u=res.first,v=res.second;
        if(dist[1][u]+w[cnt]+dist[0][v]==min_dis||dist[1][v]+w[cnt]+dist[0][u]==min_dis)
        {
            cnt+=2;
            continue;
        }
        int a=find(u),b=find(v);
        pre[a]=b;
        cnt+=2;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(find(i)==i) ans++;
    }
    if(ans==1) puts("YES");
    else puts("NO");
}

spfa代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7,M=1e6+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> PII;
ll e[M],ne[M],w[M],h[M],idx,pre[N],q[M];
ll dist[2][N],n,m;
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa(int root)
{
    memset(q,0,sizeof q);
    int k=root%n;
    int hh = 0, tt = 0;
    for (int i = 0; i <= n; i++) dist[k][i] = INF,st[i]=0;
    dist[k][root] = 0;
    q[tt++] = root, st[root] = 1;
    while (hh != tt)
    {
        ll t = q[hh++];
        st[t] = 0;
        if (hh == n) hh = 0;
        for (int i = h[t]; i != -1; i = ne[i])
            if (dist[k][e[i]] > dist[k][t] + w[i])
            {
                dist[k][e[i]] = dist[k][t] + w[i];
                if (!st[e[i]])
                {
                    st[e[i]] = 1;
                    q[tt++] = e[i];
                    if (tt == n) tt = 0;
                }
            }
    }
}
int find(int x)
{
    if(pre[x]!=x)
    {
        pre[x]=find(pre[x]);
    }
    return pre[x];
}
int main()
{
    queue<PII> ww;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n;i++) h[i]=-1,pre[i]=i;
    for(int i=0;i<m;i++)
    {
        ll a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
        ww.push({a,b});
        
    }
    spfa(1);
    spfa(n);
    ll min_dis=dist[1][n];
    int cnt=0;
    while(!ww.empty())
    {
        auto res=ww.front();
        ww.pop();
        ll u=res.first,v=res.second;
        if(dist[1][u]+w[cnt]+dist[0][v]==min_dis||dist[1][v]+w[cnt]+dist[0][u]==min_dis)
        {
            cnt+=2;
            continue;
        }
        int a=find(u),b=find(v);
        pre[a]=b;
        cnt+=2;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(find(i)==i) ans++;
    }
    if(ans==1) puts("YES");
    else puts("NO");
}