ACM-图论-SPFA poj3268模板题

本文主要是介绍ACM-图论-SPFA poj3268模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题可以用dijsktra/SPFA,我是用dijsktra先A的，然后再用SPFA试了一下，又调出来A了。

本题题意：每个点到终点的最短路（包括返回的路程），找到各条最短路中的最大值。

小重点/不TLE的方法

题目模式：去了再回来（有向图）
题解理解：
各点去终点：（取反向后，即终点（源点）到各点距离（dp/dis[i]表示）
终点回各点：（原来的edge取向，算终点（源点）到各点的距离（dp/dis[i]表示）综上可以形成一种main模式：init();//处理邻接表（head/next)SPFA();//处理dpfor(1-n)sum+=dp;uninit();//取反SPFA();//取反后的图再处理dpfor(1-n)sum+=dp;

1.分配内存

int x,n,m;
const int maxn=1e5+10;
bool vis[1010];
struct bian{//==edge int start;int end;int val;bian(int n,int v,int c):start(n),end(v),val(c){}bian(){}
}; 
bian p[maxn];
int head[maxn],next[maxn];//!!边要求要1e5++ 
int dp[1010],now[maxn];
int e;

2.两个初始化

//邻接表 
void init(){memset(head,-1,sizeof(head[0])*(n+2));memset(next,-1,sizeof(next[0])*(m+2));int a,b,c;e=0;for(int i=0;i<m;i++){scanf("%d %d %d",&a,&b,&c);addnote(a,b,c);}for(int i=1;i<=n;i++)dp[i]=inf;
}
void uninit(){memset(head,-1,sizeof(head[0])*(n+2));memset(next,-1,sizeof(next[0])*(m+2));int a,b,c;e=0;for(int i=0;i<m;i++){addnote(p[i].end,p[i].start,p[i].val);}   
}

3.邻接表的接入

void addnote(int u,int v,int c){p[e]=bian(u,v,c);next[e]=head[u]; head[u]=e;e++;
}

4.松弛操作，这里是直接修改dp值了

bool relax(int u,int v,int c){if(dp[v]>dp[u]+c){dp[v]=dp[u]+c;return true;}return false;
}

5**SPFA**

void spfa(){memset(vis,0,sizeof(vis[0])*(n+2));for(int i=1;i<=n;i++)dp[i]=inf;int sta=x;//源点/终点dp[sta]=0;int top=0;now[top++]=sta;while(top){int pre=now[--top];vis[pre]=0; //压入栈里，取出要赋值成false for(int j=head[pre];j+1!=0;j=next[j]){//无论有没有vis必须先relax(实际操作dp)，然后判断vis决定要不要入栈//if(relax()&&!vis)这样也行！！！！ if(relax(p[j].start,p[j].end,p[j].val)){if(!vis[p[j].end]){now[top++]=p[j].end;vis[p[j].end]=1;}}}}
}

6.main

int sum[1010];
int main(){//freopen("2.txt","r",stdin); //freopen("3.txt","w",stdout); while(scanf("%d %d %d",&n,&m,&x)!=EOF){int a,b,v;int ans=0;init();spfa();for(int i=1;i<=n;i++){sum[i]=0;if(i==x)continue;sum[i]+=dp[i];}uninit();spfa();for(int i=1;i<=n;i++){if(i==x)continue;sum[i]+=dp[i];ans=max(sum[i],ans);}printf("%d\n",ans);}return 0;
}