数据

5 7
1 5 10000
1 3 1000
1 4 1000
1 2 50
2 4 100
3 5 1000
4 3 500

正确答案

1650

假AC代码输出

2000

之前的假AC代码

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

typedef long long ll;

const int M = (int)1e6;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, cnt;
int head[M + 5];

struct node
{
    int v, w, nx;
}Edge[M + 5];

ll dis[M + 5];
bool vis[M + 5];

void init()
{
    cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        head[i] = -1;
        dis[i] = inf;
        vis[i] = 0;
    }
}

void add(int u, int v, int w)
{
    Edge[cnt].v = v;
    Edge[cnt].w = w;
    Edge[cnt].nx = head[u];
    head[u] = cnt++;
}

struct cmp
{
    bool operator()(int a, int b)
    {
        return dis[a] > dis[b];
    }
};
priority_queue <int, vector<int>, cmp> q;

void Dijstra(int s)
{
    dis[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int u = q.top(); q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            int v = Edge[i].v;
            if(!vis[v] && dis[v] > dis[u] + Edge[i].w)
            {
                dis[v] = dis[u] + Edge[i].w;
                q.push(v);
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m); init();
    for(int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), add(u, v, w);
    Dijstra(1);
    printf("%lld\n", dis[n] == inf ? -1 : dis[n]);
    return 0;
}