蓝桥杯_算法训练 最短路

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3
1 2 -1
2 3 -1
3 1 2

样例输出

-1
-2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

如果直接使用O(N^2)的Dijkstra的话会时间超限，所以换做优先队列优化的Dijkstra

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <math.h>
#define MAX_N 201000
#define MAX_M 21000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int u[MAX_N],v[MAX_N],w[MAX_N],first[MAX_N],next1[MAX_N];
int dis[MAX_M];
bool used[MAX_M];
int numnode,numedge;

struct node
{
    int pos;
    int cost;
    bool operator < (const node &a) const
    {
        return cost > a.cost;
    }
};

void addedge(int x,int y,int z,int k)
{
    u[k]=x;v[k]=y;w[k]=z;next1[k] = first[x];first[x] = k;
//    u[k]=y;v[k]=x;w[k]=z;next1[k]=first[y];first[y]=k++;
}

void init()
{
    int k = 0;
    memset(first,-1,sizeof(first));
    for(int i =0 ;i <numedge;i ++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z,k);
        k++;
    }
}

void Dijkstra(int startnode)
{
    memset(dis,INF,sizeof(dis));
    memset(used,false,sizeof(used));
    priority_queue<node> q;
    dis[startnode] = 0;
    node p;
    p.pos = startnode;
    p.cost = 0;
    q.push(p);
    while(!q.empty())
    {
        p = q.top();
        q.pop();
        if (used[p.pos])
            continue;
        used[p.pos] = true;
        int k = first[p.pos];
        while(k!=-1)
        {
            if (dis[v[k]] > dis[u[k]] + w[k])
            {
                dis[v[k]] = dis[u[k]] + w[k];
                if(!used[v[k]])
                {
                    p.cost = dis[v[k]];
                    p.pos = v[k];
                    q.push(p);
                }
            }
            k = next1[k];
        }
    }
}

int main()
{
    scanf("%d%d",&numnode,&numedge);
    init();
    Dijkstra(1);
    for(int i = 2;i <= numnode;i ++)
        printf("%d\n",dis[i]);
}