首页 > ACM题库 > HDU-杭电 > hdu 2290 Find the Path-最短路径[解题报告]C++
2014
01-05

hdu 2290 Find the Path-最短路径[解题报告]C++

Find the Path

问题描述 :

Scofield is a hero in American show "Prison Break". He had broken the prison and started a big runaway.
Scofield has a map of US with cities and bidirectional roads between them. The lengths of roads are known. Some cities get a lot of cops who are very troublesome. Now Scofield needs your help to arrange his runaway route.

He needs a shortest path between two cities, while the quantity of the police in any city, except the start city and end city, on the route is no more than k.

You should know that it is very hard to escape. Scofield is very smart but not good at computer. Now Scofield is in trouble, can you help him with your computer?

输入:

The input consists of several test cases. There is an integer T on the first line indicating the number of test cases.
For each case, the first line consists of two integers N and M. N is the number of cities; M is the number of roads. The next line contains N integers C1, C2… CN, where Ci is the number of cops in city i.

Then followed M lines, each line consists of three integer, u, v, w, indicating there is a road with length w between city u and city v.

The following line consists of an integer Q, indicating the number of queries. Each of the following Q lines consists of three integers, u, v, k, indicating the query for the shortest path between city u and city v with limitation of k cops.

Technical Specification

1. T ≤ 20
2. 2 ≤ N ≤ 200, 0 ≤ M ≤ n * (n � 1) / 2
3. 0 ≤ Ci ≤ 1000,000,000
4. 0 ≤ u, v < N, 0 ≤ w ≤ 1000, 0 ≤ k ≤ 1000,000,000
5. 0 ≤ Q ≤ 100000
6. There is no more than ONE road between two cities and no road between the same cities.
7. For each query, u is not equal to v.
8. There is ONE empty line after each test case.

输出:

The input consists of several test cases. There is an integer T on the first line indicating the number of test cases.
For each case, the first line consists of two integers N and M. N is the number of cities; M is the number of roads. The next line contains N integers C1, C2… CN, where Ci is the number of cops in city i.

Then followed M lines, each line consists of three integer, u, v, w, indicating there is a road with length w between city u and city v.

The following line consists of an integer Q, indicating the number of queries. Each of the following Q lines consists of three integers, u, v, k, indicating the query for the shortest path between city u and city v with limitation of k cops.

Technical Specification

1. T ≤ 20
2. 2 ≤ N ≤ 200, 0 ≤ M ≤ n * (n � 1) / 2
3. 0 ≤ Ci ≤ 1000,000,000
4. 0 ≤ u, v < N, 0 ≤ w ≤ 1000, 0 ≤ k ≤ 1000,000,000
5. 0 ≤ Q ≤ 100000
6. There is no more than ONE road between two cities and no road between the same cities.
7. For each query, u is not equal to v.
8. There is ONE empty line after each test case.

样例输入:

1
4 4
100 2 3 100
0 1 1
0 2 1
1 3 2
2 3 3
2
0 3 2
0 3 1

样例输出:

3
-1


floyed算法的应用

/*

核心思路  通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

  从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

  采用的是(松弛技术),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

  其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}

  map[i,j]表示i到j的最短距离

  K是穷举i,j的断点

  map[n,n]初值应该为0,或者按照题目意思来做。

  当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路

*/ 摘自百度百科

#include <iostream>
#include <cstdio>

using namespace std;
#define INF 10000000
struct Node
{
    int num,id;       
    bool operator<(Node a) const
    {
         return num < a.num;     
    }
}cop[210];
int pos[210],dp[210][210][210];

int main()
{
    int n,m,ca;
    scanf("%d",&ca);
    while(ca--)
    {
         scanf("%d %d",&n,&m);     
         for(int i=0;i<n;i++)                
         {
            scanf("%d",&cop[i].num);        
            cop[i].id=i;
         }
         sort(cop,cop+n);
         for(int i=0;i<n;i++)
           pos[cop[i].id]=i+1;
         for(int i=1;i<=n;i++)  
         for(int j=1;j<=n;j++)
            dp[i][j][0]=INF;
         int a,b,c;
         for(int i=0;i<m;i++)  
         {
               scanf("%d %d %d",&a,&b,&c);        
               dp[pos[a]][pos[b]][0]=dp[pos[b]][pos[a]][0]=c;
         } 
         for(int k=1;k<=n;k++)
         {
             for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
               dp[i][j][k]=dp[i][j][k-1];
             for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
               dp[i][j][k]=min(dp[i][j][k],dp[i][k][k-1]+dp[k][j][k-1]);
         }
         int Q;
         scanf("%d",&Q);
         while(Q--)
         {
              scanf("%d %d %d",&a,&b,&c); 
              int ans=dp[pos[a]][pos[b]][0];
              for(int i=n-1;i>=0;i--)         
                if(cop[i].num<=c) {ans=dp[pos[a]][pos[b]][i+1];break;}
              if(ans==INF) puts("-1");  
              else printf("%d\n",ans);
         }
         printf("\n");
    }
    return 0;    
}

 


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。