邻接表求调，16分

n_bluetea @ 2024-03-11 12:00:10

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

void dijkstra(vector<vector<pair<long long,long long>>>& graph,vector<long long>&dis,long long start)
{
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> pq;
    dis[start] = 0;

    pq.push(make_pair(0, start));
    while (!pq.empty())
    {
        long long    u = pq.top().second;
        long long dist = pq.top().first;
        pq.pop();

        if (dist > dis[u]) continue;
        for (int i = 0; i < graph[u].size(); i++)
        {
            long long      v = graph[u][i].first;
            long long weight = graph[u][i].second;

            if (dis[u] != 1e9 && weight != 1e9 && dis[v] > dis[u] + weight) {
                dis[v] = dis[u] + weight;
                pq.push(make_pair(dis[v], v));
            }
        }
    }

}
int main()
{
    int n, m, s;
    cin >> n >> m >> s;

    vector<long long> dis(n + 1, 1e9);
    vector < vector<pair<long long, long long>>> graph(n + 1);
    for (int i = 1; i <= n; i++)
    {
        long long x, y, w;
        cin >> x >> y >> w;
        graph[x].push_back({ y,w });
    }

    dijkstra(graph,dis,s);

    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}

by SpeedStar @ 2024-03-11 12:11:17

@n_blutea 答案可以取到1e9

by n_bluetea @ 2024-03-11 12:14:16

@寒烟冷浅暮殇 把限制条件去掉就变成零分了

by SpeedStar @ 2024-03-11 12:17:29

@n_blutea 我的意思是你可以把无穷大调大点，比如1001001001

by ccf666 @ 2024-03-11 12:45:34

可以把定义里面的1e9调大一点

by n_bluetea @ 2024-03-11 19:35:40

@寒烟冷浅暮殇

谢谢，但是我改成1e10还是全wa了

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

void dijkstra(vector<vector<pair<long long,long long>>>& graph,vector<long long>&dis,long long start)
{
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
    dis[start] = 0;

    pq.push(make_pair(0, start));
    while (!pq.empty())
    {
        long long    u = pq.top().second;
        long long dist = pq.top().first;
        pq.pop();

        if (dist > dis[u]) continue;
        for (int i = 0; i < graph[u].size(); i++)
        {
            long long      v = graph[u][i].first;
            long long weight = graph[u][i].second;

            if (dis[v] > dis[u] + weight) {
                dis[v] = dis[u] + weight;
                pq.push(make_pair(dis[v], v));
            }
        }
    }

}
int main()
{
    int n, m, s;
    cin >> n >> m >> s;

    vector<long long> dis(n + 100, 1e10);
    vector < vector<pair<long long, long long>>> graph(n + 100);
    for (int i = 1; i <= n; i++)
    {
        long long x, y, w;
        cin >> x >> y >> w;
        graph[x].push_back({ y,w });
    }

    dijkstra(graph,dis,s);

    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}

by SpeedStar @ 2024-03-11 20:06:11

@n_blutea 你再看看你读了多少条边

by n_bluetea @ 2024-03-11 20:21:59

@寒烟冷浅暮殇 过了，十分感谢，关注了