错两个点，呜呜呜

szm111213 @ 2024-07-18 10:31:40

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct node
{
    int y,z;
};
vector<node>g[1000100];
int dis[1000010],vis[1000010];
void dij(int st)
{
    priority_queue<pair<int ,int>>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[st] = 0;
    q.push({0,st});
    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if(vis[x])
        {
            continue;
        }
        vis[x] = 1;
        for(auto to : g[x])
        {
            int y = to.y;
            int z = to.z;
            if(dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                if(vis[y] == 0)
                {
                    q.push({-dis[y],y});
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    dij(s);
    for(int i=1;i<=n;i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}

by szm111213 @ 2024-07-18 10:33:02

哦，我明白了，这道题是单向边

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct node
{
    int y,z;
};
vector<node>g[1000100];
int dis[1000010],vis[1000010];
void dij(int st)
{
    priority_queue<pair<int ,int>>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[st] = 0;
    q.push({0,st});
    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if(vis[x])
        {
            continue;
        }
        vis[x] = 1;
        for(auto to : g[x])
        {
            int y = to.y;
            int z = to.z;
            if(dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                if(vis[y] == 0)
                {
                    q.push({-dis[y],y});
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
    }
    dij(s);
    for(int i=1;i<=n;i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}