HDU 3790 最短路径有关问题

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;
}