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_is​i​​、ti t_it​i​​、wi(1≤wi≤109) w_i(1 leq w_i leq 10 ^ 9)w​i​​(1≤w​i​​≤10​9​​)，表示一条从 si s_is​i​​ 到 ti t_it​i​​ 长度为 wi w_iw​i​​ 的边。

输出格式

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

样例

样例输入

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

样例输出

7

屠龙宝刀点击就送

#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <queue>
#define N 6205

using namespace std;
void read(int &x)
{
    x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
}
struct node
{
    int next,to,dis;
}edge[N<<1];
int head[N/2],cnt,n,m,s,t,dis[N/2];
bool visit[N/2];
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,1,sizeof(dis));
    dis[s]=0;
    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]=1;
        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 0;
}