最短路径问题

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

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

3 2

1 2 5 6

2 3 4 5

1 3

0 0

Sample Output

9 11

 //2016.4.21

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 const int inf = ;

 int Tu_dist[maxn][maxn], Tu_pay[maxn][maxn], dis[maxn], pay[maxn], book[maxn];

 int n, m;

 void dijkstra(int s);

 int main()

 {

     while(cin>>n>>m&&n&&m)

     {

         for(int i = ; i <= n; i++)

             for(int j = ; j <= n; j++)

             {

                 Tu_dist[i][j] =inf;

                 Tu_pay[i][j] = inf;

             }

         int a, b, d, p, s, t;

         while(m--)

         {

             scanf("%d%d%d%d", &a, &b, &d, &p);

             if(d<Tu_dist[a][b])

             {

                 Tu_dist[a][b] = Tu_dist[b][a] = d;

                 Tu_pay[a][b] = Tu_pay[b][a] = p;

             }

         }

         scanf("%d%d", &s, &t);

         dijkstra(s);

         printf("%d %d\n", dis[t], pay[t]);

     }

     return ;

 }

 void dijkstra(int s)

 {

     int mindist, u, v;

     for(int i = ; i <= n; i++)

     {

         dis[i] = Tu_dist[s][i];

         pay[i] = Tu_pay[s][i];

     }

     memset(book, , sizeof(book));

     book[s] = ;

     dis[s] = ;

     pay[s] = ;

     for(int i = ; i < n; i++)

     {

         mindist = inf;

         for(int j = ; j <= n; j++)

         {

             if(book[j]==&&dis[j]<mindist)

             {

                 mindist = dis[j];

                 u = j;

             }

         }

         book[u] = ;

         for(int v = ; v <= n; v++)

         {

             if(!book[v] && Tu_dist[u][v]<inf)

             {

                 if(dis[v]>dis[u]+Tu_dist[u][v])

                 {

                     dis[v] = dis[u]+Tu_dist[u][v];

                     pay[v] = pay[u]+Tu_pay[u][v];

                 }

                 else if(dis[v]==(dis[u]+Tu_dist[u][v]))

                     pay[v] = (pay[u]+Tu_pay[u][v])<pay[v]?pay[u]+Tu_pay[u][v]:pay[v];

             }

         }

     }

 }

巴特西

HDU3790