首页 > 代码库 > C(最短路_spfa+前向星)
C(最短路_spfa+前向星)
C
Time Limit: 7000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。
输入
多组输入。
对于每组数据。
第一行输入n,m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。
接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。
最后输入s,e。
接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。
最后输入s,e。
输出
对于每组数据输出一个整数代表答案。
示例输入
3 1 1 2 3 1 2
示例输出
3
提示
来源
zmx
示例程序
卡数据卡的太厉害了,差点超内存,spfa+前向星果断水过,但是TLE了好几次,我又把代码删掉重新写的,然后AC了 ,都一样 不知道为什么,在下面贴出来,希望各路大神给找找,万分感谢。
TLE的代码 7010ms
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <queue> #include <string> using namespace std; #define inf 1e19+7 struct node { int v,w; int next; } edge[2000010]; int dis[500010]; int vis[500010]; int head[500010]; int cnt; int n; void add(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void SPFA(int s,int e) { int i; queue<int>q; memset(vis,0,sizeof(vis)); for(i=0; i<=n; i++) dis[i]=inf; dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { int m,i; int u,v,w; int s,e; while(~scanf("%d %d",&n,&m)) { memset(head,-1,sizeof(head)); cnt=0; for(i=1; i<=m; i++) { scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d %d",&s,&e); SPFA(s,e); printf("%d\n",dis[e]); } return 0; }
AC代码 1200ms
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <queue> #include <string> using namespace std; #define inf 999999999 struct node { int v,w; int next; }edge[4000010]; int dis[500010]; int vis[500010]; int head[500010]; int cnt; int n; void add(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void SPFA(int s,int e) { int i; queue<int>q; memset(vis,0,sizeof(vis)); for(i=0; i<=n; i++) { dis[i]=inf; } dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { int m; int u,v,w; int s,e; while(~scanf("%d %d",&n,&m)) { memset(head,-1,sizeof(head)); cnt=0; while(m--) { scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d %d",&s,&e); SPFA(s,e); printf("%d\n",dis[e]); } return 0; }
C(最短路_spfa+前向星)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。