首页 > 代码库 > hdu3790最短路径问题
hdu3790最短路径问题
这是一个最短路径的裸题,我们在边结构体中 添加成员路径和花费,然后在松弛操作的时候用这两个来松弛就OK
// AC 840k 109ms #include<cstdio> #include<queue> using namespace std; #define MAX 1001 #define IFN 1<<30-1 struct node { int to,len,cost,next; }edge[MAX*100*2]; int head[MAX],tol; int n,m,st,end; void init() { int i; for(i=1;i<=n;i++) head[i]=-1; tol=0; int a,b,l,c; for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&l,&c); edge[tol].to=b,edge[tol].len=l,edge[tol].cost=c; edge[tol].next=head[a]; head[a]=tol++; edge[tol].to=a,edge[tol].len=l,edge[tol].cost=c; edge[tol].next=head[b]; head[b]=tol++; } scanf("%d%d",&st,&end); } int d[MAX],cost[MAX]; bool flag[MAX]; int main() { while(scanf("%d%d",&n,&m),n+m) { init(); int i; for(i=1;i<=n;i++) d[i]=IFN,cost[i]=IFN,flag[i]=false; d[st]=0,cost[st]=0; queue<int>q; q.push(st); while(!q.empty()) { int u=q.front();q.pop();flag[u]=false; for(int j=head[u];j!=-1;j=edge[j].next) { int v=edge[j].to,l=edge[j].len,c=edge[j].cost; if(d[v]>d[u]+l || (d[v]==d[u]+l) && cost[v]>cost[u]+c) { d[v]=d[u]+l;cost[v]=cost[u]+c; if(!flag[v]) q.push(v),flag[v]=true; } } } printf("%d %d\n",d[end],cost[end]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。