@zzzc18
2017-11-10T11:28:46.000000Z
字数 1218
阅读 1832
最短路
深搜版的
使用贪心预处理以及迭代加深,可以得出一个高效的深搜
具体细节可以直接看上面的论文
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long LL;
const int MAXN = 10000+9;
const int MAXM = 500000+9;
int n,m;
struct E{
int next,to;
LL val;
}edge[MAXM];
int head[MAXN],edge_num;
int S;
LL dis[MAXN];
void addedge(int x,int y,LL v){
edge[++edge_num].next=head[x];
edge[edge_num].to=y;
edge[edge_num].val=v;
head[x]=edge_num;
}
void Build(){
scanf("%d%d%d",&n,&m,&S);
for(int i=1;i<=m;i++){
int a,b;
LL c;
scanf("%d%d%lld",&a,&b,&c);
addedge(a,b,c);
}
for(int i=1;i<=n;i++)
dis[i]=INT_MAX;
dis[S]=0;
}
bool SPFA_INIT(int x,int step,int lim){
if(step==lim)return true;
for(int i=head[x];i;i=edge[i].next){
if(dis[edge[i].to]>dis[x]+edge[i].val){
dis[edge[i].to]=dis[x]+edge[i].val;
SPFA_INIT(edge[i].to,step+1,lim);
return true;
}
}
return false;
}
void SPFA(int x,int step,int lim){
if(step==lim)
return;
for(int i=head[x];i;i=edge[i].next){
if(dis[edge[i].to]>dis[x]+edge[i].val){
dis[edge[i].to]=dis[x]+edge[i].val;
SPFA(edge[i].to,step+1,lim);
}
}
}
int main(){
Build();
for(int i=0;(1<<i-1)<=n;i++){
int depth=1<<i;
for(int j=1;j<=n;j++){
if(SPFA_INIT(j,0,depth)){
for(int k=1;k<=n;k++){
SPFA(k,0,depth);
}
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}