HDU 3790 最短路径问题（经典呀）

最短路径问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4184 Accepted Submission(s): 1249

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)

Output

输出一行有两个数，最短距离及其花费。

Sample Input

Sample Output

9 11

Source

浙大计算机研究生复试上机考试-2010年

Recommend

notonlysuccess

//第一次遇见带了费用的最短路径、呵呵、1Y，幸福感呀

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 1003
using namespace std;
struct node
{
    int d,p;
};
node map[N][N];
bool b[N];
int n,s,t;
void dijk()
{
   memset(b,0,sizeof(b));
   b[s]=1;
   int i,j,min,m=n;
   while(--m)
   {
       min=1000000;
       for(i=1;i<=n;i++)
         if(!b[i])
         {
             if(map[s][i].d<min)
             {
                min=map[s][i].d;
                 j=i;
             }else if(min<1000000&&map[s][i].d==min)
             {
                 if(map[s][i].p<map[s][j].p)
                    j=i;
             }
         }
      b[j]=1;
      for(i=1;i<=n;i++)
        if(!b[i])
        {
            if(map[s][i].d>map[s][j].d+map[j][i].d)
             {
                 map[s][i].d=map[s][j].d+map[j][i].d;
                 map[s][i].p=map[s][j].p+map[j][i].p;
             }
             else if(map[s][i].d==map[s][j].d+map[j][i].d)
             {
                 if(map[s][i].p>map[s][j].p+map[j][i].p)
                   map[s][i].p=map[s][j].p+map[j][i].p;
             }
        }
   }
   printf("%d %d\n",map[s][t].d,map[s][t].p);
}
int main()
{
    int m;
    int i,j,d,p;
    while(scanf("%d%d",&n,&m),n||m)
    {
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            map[i][j].d=1000000;
       while(m--)
       {
           scanf("%d%d%d%d",&i,&j,&d,&p);
           if(map[i][j].d>d)
           {
              map[j][i].d=map[i][j].d=d;
              map[j][i].p=map[i][j].p=p;
           }
           else if(map[i][j].d==d&&map[i][j].p>p)
           {
               map[j][i].p=map[i][j].p=p;
           }
       }
       scanf("%d%d",&s,&t);
       dijk();
    }
    return 0;
}