LibreOJ #119. 最短路 (堆优化dijkstra)

题目描述

给一个 n(1≤2500≤n) n(1 \leq 2500 \leq n)n(1≤2500≤n) 个点 m(1≤6200≤m) m(1 \leq 6200 \leq m)m(1≤6200≤m) 条边的无向图，求 s ss 到 t tt 的最短路。

输入格式

第一行四个由空格隔开的整数 n nn、m mm、s ss、t tt。
之后的 m mm 行，每行三个正整数 si s_isi、ti t_iti、wi(1≤wi≤109) w_i(1 \leq w_i \leq 10 ^ 9)wi(1≤wi≤109)，表示一条从 si s_isi 到 ti t_iti 长度为 wi w_iwi 的边。

输出格式

一个整数表示从 s ss 到 t tt 的最短路长度。数据保证至少存在一条道路。

样例

样例输入

样例输出

屠龙宝刀点击就送

#include <ctype.h>

#include <cstring>

#include <cstdio>

#include <queue>

#define N 6205

using namespace std;

void read(int &x)

{

    x=;

    char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) x=x*+ch-'',ch=getchar();

}

struct node

{

    int next,to,dis;

}edge[N<<];

int head[N/],cnt,n,m,s,t,dis[N/];

bool visit[N/];

struct NODE

{

    int x,y;

    bool operator<(NODE a)const

    {

        return x>a.x;

    }

};

priority_queue<NODE>q;

void add(int u,int v,int w)

{

    edge[++cnt].next=head[u];

    edge[cnt].to=v;

    edge[cnt].dis=w;

    head[u]=cnt;

}

int main()

{

    read(n);read(m);read(s);read(t);

    for(int si,ti,wi;m--;)

    {

        read(si);

        read(ti);

        read(wi);

        add(si,ti,wi);

        add(ti,si,wi);

    }

    memset(dis,,sizeof(dis));

    dis[s]=;

    NODE a;

    a.x=dis[s];

    a.y=s;

    q.push(a);

    while(!q.empty())

    {

        NODE a=q.top();

        q.pop();

        if(visit[a.x]) continue;

        int v=a.y;

        visit[v]=;

        for(int i=head[v];i;i=edge[i].next)

        {

            if(dis[edge[i].to]>edge[i].dis+dis[v])

            {

                dis[edge[i].to]=edge[i].dis+dis[v];

                NODE a;

                a.x=dis[edge[i].to];

                a.y=edge[i].to;

                q.push(a);

            }

        }

    }

    printf("%d",dis[t]);

    return ;

}

巴特西