P3371 【模板】单源最短路径（弱化版）

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15；

对于40%的数据：N<=100，M<=10000；

对于70%的数据：N<=1000，M<=100000；

对于100%的数据：N<=10000，M<=500000。保证数据随机。

对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

P3371 【模板】单源最短路径（弱化版）

图片1到3和1到4的文字位置调换

思路：看到N<=10000,想到了Dijkstra进行堆优化，但是只得了70分，加入链式前向星后，并且将队列改为pair后过了。。。

代码如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
#define INF 2147483647
typedef pair<int,int>pii;
int dis[10005];
int cnt=0;
int read()//读入优化
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
struct Edge
{
    int u,v,w;
    //Edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){};
};
//struct Node
//{
//    int id;
//    int w;
//    bool operator<(const Node &b)
//        const {w>b.w;}
//}mid;
int head[10005];
Edge e[500005];
priority_queue<pii,vector<pii>,greater<pii> >q;
void add(int a,int b,int c)
{
    e[++cnt].u=head[a];
    e[cnt].v=b;
    e[cnt].w=c;
    head[a]=cnt;
}
void Dijkstre(int s)
{
    q.push({s,0});
    dis[s]=0;
    while(!q.empty())
    {
        pii mid=q.top();
        q.pop();
        int crd=mid.first;
        if(mid.second!=dis[crd])continue;
        for(int i=head[mid.first];i!=-1;i=e[i].u)
        {
            if(dis[e[i].v]>dis[crd]+e[i].w)
            {
                dis[e[i].v]=dis[crd]+e[i].w;
                q.push({e[i].v,dis[e[i].v]});
            }
        }
    }
}
int main()
{
    int n,m,s;
    n=read();m=read();s=read();
    memset(head,-1,sizeof(head));
    for(int i=0;i<=n;i++)dis[i]=INF;
     int a,b,c;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    Dijkstre(s);
    for(int i=1;i<=n;i++)
    {
        printf("%d%c",dis[i],(i==n)?'\n':' ');
    }
}

P3371 【模板】单源最短路径（弱化版）

题目背景

题目描述

输入输出格式

输入输出样例

说明

相关推荐