洛谷 3371_单源最短路径_spfa

2019-11-06 07:50:51

字体：大中小

来源：转载

供稿：网友

题目描述

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

思路

一个普通的spfa 然后注意的是题目中给定了最大值！！！！！ O(KE)

#include <stdio.h>#include <queue>#include <iostream>#define maxn 500001#define INF 2147483647using namespace std;int l=0,s;struct arr { long long x,y,w,next; };long long x,y,z;arr edge[maxn];int ls[maxn];long long state[maxn];bool exits[maxn];int spfa(){ long long i; queue <long long> t; t.push(s); state[s]=0; exits[s]=true; do { long long tt=t.front(); t.pop(); i=ls[tt]; while (i!=0) { if (state[edge[i].x]+edge[i].w<=state[edge[i].y]) { state[edge[i].y]=state[edge[i].x]+edge[i].w; if (exits[edge[i].y]==false) { t.push(edge[i].y); exits[edge[i].y]=true; } } i=edge[i].next; } exits[tt]=false; } while (!t.empty());}int main(){ int j,k,n,m; scanf("%d%d%d",&n,&m,&s); for (int i=1;i<=m;i++) { l++; scanf("%lld%lld%lld",&x,&y,&z); edge[l].x=x; edge[l].y=y; edge[l].w=z; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l; } for (int i=1;i<maxn;i++) state[i]=INF; spfa(); for (int i=1;i<=n;i++) PRintf("%lld ",state[i]);}

上一篇：char *和char[]的初始化

下一篇：变量、数据类型和运算符