洛谷 P3371 【模板】单源最短路径(弱化版)(堆,bfs,最短路)

发布于:2021-12-02 11:39:13

?


题目背景

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


题目描述

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


输入输出格式

输入格式:


?


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


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


?


输出格式:


?


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


?


输入输出样例

输入样例#1:?复制


4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例#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。请注意,该题与本题数据范围略有不同。


样例说明:



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


?


看了正月点灯笼的视频 ?想看视频点传送 ? ? 传送


让我了解了bfs最短路 ?和 对优先队列的深入了解(大根堆 ?小根堆);


关于优先队列可以参考我前面的博客;


思路:先用静态链表存图,然后用用结构体建立一个自己想要的优先队列;然后bfs存点;


此题是弱化版,所以数据有点水,用弱化版的代码过不了标准版Orz;


历经千辛万苦优化成功,下面的代码两道题都能过


#include
#include
#include
#include
#include
#include
#define maxn 200005
#define inf 0x3f3f3f3f
typedef long long ll;

using namespace std;

ll n,m,k;
ll dis1[maxn],dis2[maxn];
bool flag[maxn];
struct node
{
ll x;
ll d;
node(ll xx,ll dd):x(xx),d(dd){};
};
bool operator < (const node a,const node b)
{
return a.d > b.d;
}
vector< pair > p[maxn];
void dij(ll k)
{
priority_queueq;

fill(dis1,dis1+n+1,inf);
fill(dis2,dis2+n+1,inf);

dis1[k] = 0;
q.push(node(1,0));
while(!q.empty())
{
node now = q.top();
q.pop();
if(flag[now.x])continue;
flag[now.x] = 1;
for(int i = 0; i < p[now.x].size(); i ++)
{
ll v = p[now.x][i].first;
ll w = p[now.x][i].second;
ll d = dis1[now.x] + w;
if(dis1[v] > d && !flag[v])
{
dis1[v] = d;
q.push(node(v,dis1[v]));
}

// if(dis2[v] > d && dis1[v] < d)
// {
// dis2[v] = d;
// q.push(node(v,dis2[v]));
// }
}
}

//printf("%lld
",dis2[n]);
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
scanf("%lld%lld%lld",&n,&m,&k);

for(int i = 1; i <= m; i ++)
{
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
p[a].push_back(make_pair(b,c));
//p[b].push_back(make_pair(a,c));
}

dij(k);

for(int i = 1; i <= n; i ++)
{
cout << dis1[i] << " ";
}
cout << endl;

return 0;
}

?

相关推荐

最新更新

猜你喜欢