HDU 3790 最短路径问题 (SPFA)
转载请注明出处：http://blog.csdn.net/a1dark
分析：比一般最短路多了一个花费、多加一个判断即可、用的SPFA、这道题让我搞清楚了以前定义INF为啥爆的问题、受益颇多、
#include<stdio.h>#include<queue>#include<string.h>#include<algorithm>using namespace std;#define INF 0x7fffffff#define N 1005struct node{ int len,cost;}map[N][N];node dist[N];int vis[N];int m,n;void spfa(int x){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ dist[i].len=INF; dist[i].cost=INF; } dist[x].len=0; dist[x].cost=0; queue<int >q; q.push(x); vis[x]=1; while(!q.empty()){ int now=q.front(); q.pop(); vis[now]=0; for(int i=1;i<=n;i++){ if(map[now][i].len+dist[now].len<dist[i].len&&map[now][i].len!=INF){ dist[i].len=map[now][i].len+dist[now].len; printf("%d\n",map[now][i].len); dist[i].cost=map[now][i].cost+dist[now].cost; if(!vis[i]){ q.push(i); vis[i]=1; } } if(map[now][i].len+dist[now].len==dist[i].len&&map[now][i].cost+dist[now].cost<dist[i].cost){ map[now][i].cost+dist[now].cost==dist[i].cost; } } }}void init(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i==j){ map[i][j].len=0; map[i][j].cost=0; } else{ map[i][j].len=INF; map[i][j].cost=INF; } }}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0)break; init(); int s,e,d,p; for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&s,&e,&d,&p); if(d<map[s][e].len){ map[s][e].len=d; map[e][s].len=d; map[s][e].cost=p; map[e][s].cost=p; } else if(d==map[s][e].len&&p<map[s][e].cost){ map[s][e].cost=p; map[e][s].cost=p; } } int st,ed; scanf("%d%d",&st,&ed); spfa(st); printf("%d %d\n",dist[ed].len,dist[ed].cost); } return 0;}