欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3371 【模板】单源最短路径(弱化版)

程序员文章站 2022-06-03 21:06:33
...

P3371 【模板】单源最短路径(弱化版)
P3371 【模板】单源最短路径(弱化版)

这道题虽是模板题,但是有毒瘤数据,我被这个点坑惨了

下面是毒瘤数据之一

5 15 5
2 5 181
1 5 98
4 2 49
3 2 262
4 3 26
2 4 192
5 1 221
2 2 254
4 4 233
1 5 44
5 4 67
4 2 214
1 1 47
1 1 118
5 4 3

看到没,有两个1–5,第一个1 5 98 第二个 1 5 44

也就是存储路程的时候还要考虑最小的路程,上面我们肯定存储44

如果不考虑这个就会导致前面路程短,后面的路程长就会覆盖前面短的路程,怎么样?够毒瘤吧~

下面是AC代码~

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;
#define  Max 10005
#define INF 2147483647
typedef pair<int,int> Node; //存放顶点和边权值
vector<Node > Grap[Max]; //顶点i--顶点.first
bool flag[Max];
int d[Max];
void Dijkstra(int n,int s);
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    int u,v,w;
    Node t;
    bool k;
    fill(d,d+Max,INF);
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        t.first=v;
        t.second=w;
        k=true;
        for(int i=0;i<Grap[u].size();i++)
        {
            if(Grap[u][i].first==v)
            {
                k=false;
                if(Grap[u][i].second>w)
                {
                    Grap[u][i].second=w;
                }
                break;
            }
        }
        if(k)
        {
            Grap[u].push_back(t);
        }
    }
    memset(flag,false, sizeof(flag));
    Dijkstra(n,s);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}


void Dijkstra(int n,int s)
{
    d[s]=0;
    for(int j=1;j<=n;j++)
    {
        int u=-1,Min=INF;
        for(int i=1;i<=n;i++)
        {
            if(!flag[i]&&d[i]<Min)
            {
                u=i;
                Min=d[i];
            }
        }
        if(u==-1)
        {
            return ;
        }
        flag[u]=true;
        for(int i=0;i<Grap[u].size();i++)
        {
            int v=Grap[u][i].first;
            if(!flag[v]&&Grap[u][i].second+d[u]<d[v])
            {
                d[v]=Grap[u][i].second+d[u];
            }
        }
    }
}
相关标签: