Dijkstra算法——最短路径

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

const int maxn=100000+15;
const int maxm=100000+15;
const int oo=100000000;
struct Edge
{
    int x,y,z,next;
    Edge(int x=0,int y=0,int z=0,int next=0):x(x),y(y),z(z),next(next) {}
}edge[maxm];
int n,m;
int sumedge,head[maxn];
int dis[maxn];
int ins(int x,int y,int z)
{
    edge[++sumedge]=Edge(x,y,z,head[x]);
    return head[x]=sumedge;
}
struct Node
{
    int x,v;
    Node(int x=0,int v=0):x(x),v(v){}
};
const bool operator < (const Node &a,const Node &b)
{
    return a.v<b.v;
}
priority_queue <Node> que;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        ins(x,y,z);
    }
    for (int i=2;i<=n;i++) dis[i]=-oo;
    que.push(Node(1,oo));
    for (int i=1;i<=n;i++)
    {
        Node temp=que.top();
        for (;dis[temp.x]!=temp.v;que.pop(),temp=que.top());
        que.pop();
        for (int u=head[temp.x];u;u=edge[u].next)
         if (dis[edge[u].y]<min(temp.v,edge[u].z))
         {
             dis[edge[u].y]=min(temp.v,edge[u].z);
             que.push(Node(edge[u].y,dis[edge[u].y]));
         }
    }
    for (int i=1;i<=n;i++) printf("%d ",dis[i]);
    printf("\n");
    return 0;
 }