前向星解法，除了 1,3 AC以外一片红

2点数据输出一片2^31-1

以下是代码

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

struct side
{
    int start, end, w;
};

side graph[500001];
int head[10001];
int dist[10001];
bool walked[10001];
int n, m, s;

bool cmp(side a, side b)
{
    return a.start==b.start ? a.end<b.end : a.start<b.start;
}

void djs()
{
    int minDist = INT_MAX, minNode;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
            if (!walked[j] && dist[j]<minDist)
                {
                    minDist = dist[j];
                    minNode = j;
                }
        walked[minNode] = 1;
        for (int t=head[minNode]; t<m && graph[t].start==minNode; t++)
        {
            if (dist[graph[t].end] > dist[minNode]+graph[t].w)
            {
                // printf("%d: Use %d to %d, %d->%d\n",
                //  i, minNode, graph[t].end, dist[graph[t].end], dist[minNode]+graph[t].w);
                dist[graph[t].end] = dist[minNode]+graph[t].w;
            }
        }
        // for (int h=1; h<=n; h++) printf("%d ", dist[h]);
        // printf("\n");
    }
}

int main()
{
    // #ifndef ONLINE_JUDGE
    //     freopen("IO\\stdin.in", "r", stdin);
    //     freopen("IO\\stdout.out", "w", stdout);
    // #endif
    scanf("%d%d%d", &n, &m, &s);
    for (int i=0; i<m; i++)
        scanf("%d%d%d", &graph[i].start, &graph[i].end, &graph[i].w);
    
    sort(graph, graph+m, cmp);
    head[graph[0].start] = 0;
    for (int i=0; i<m; i++)
        if (graph[i-1].start != graph[i].start)
            head[graph[i].start] = i;
    
    for (int i=1; i<=n; i++)
        dist[i] = INT_MAX;

    for (int i=head[s]; i<m && graph[i].start==s; i++)
        dist[graph[i].end] = min(graph[i].w, dist[graph[i].end]);
    dist[s] = 0;
    walked[s] = 1;
    // for (int i=1; i<=n; i++) printf("%d ", dist[i]);
    // printf("\n");
    djs();

    for (int i=1; i<=n; i++)
        printf("%d ", dist[i]);
    return 0;
}