HDU 3790 最短路径问题
是一个不错的dijkstra练手题。
其实题目要求的只是最短路径，而那个费用是再这条路径上的最少费用；
只要在最短长度时取最小费用；
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=1005;const int INF=1<<28;struct Node{ int l,v;}path[N][N],d[N];bool s[N];int min_v;void Init(int n){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { path[i][j].l=path[i][j].v=INF; } for(i=1;i<=n;i++) d[i].l=d[i].v=INF;}int dijkstra(int first,int last,int n){ int i,j,u; memset(s,false,sizeof(s)); for(i=1;i<=n;i++) { d[i].l=path[first][i].l; d[i].v=path[first][i].v; } d[first].l=d[first].v=0; for(i=0;i<n;i++) { int temp=INF; for(j=1;j<=n;j++) { if(!s[j]&&d[j].l<temp) { temp=d[j].l; u=j; } } s[u]=true; for(j=1;j<=n;j++) { if(!s[j]&&d[j].l>d[u].l+path[u][j].l) { d[j].l=d[u].l+path[u][j].l; d[j].v=d[u].v+path[u][j].v; } if(!s[j]&&d[j].l==d[u].l+path[u][j].l&&d[j].v>d[u].v+path[u][j].v)//此处判断比较重要 d[j].v=d[u].v+path[u][j].v; } } min_v=d[last].v; return d[last].l;}int main(){ int n,m,i,a,b,d,p; int first,last,ans; while(scanf("%d%d",&n,&m)&&(n+m)) { Init(n); for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&d,&p); if(d<path[a][b].l) { path[a][b].l=path[b][a].l=d;//图为无向图 path[a][b].v=path[b][a].v=p; } if(d==path[a][b].l&&p<path[a][b].v)//判断关键 path[a][b].v=path[b][a].v=p; } scanf("%d%d",&first,&last); ans=dijkstra(first,last,n); printf("%d %d\n",ans,min_v); } return 0;}