程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 4034 Graph(深化最短路floyd)

hdu 4034 Graph(深化最短路floyd)

編輯:關於C++

 

 

Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2188 Accepted Submission(s): 1101

Problem Description Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph?
Input The first line is the test case number T (T ≤ 100).
First line of each case is an integer N (1 ≤ N ≤ 100), the number of vertexes.
Following N lines each contains N integers. All these integers are less than 1000000.
The jth integer of ith line is the shortest path from vertex i to j.
The ith element of ith line is always 0. Other elements are all positive.

Output For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then one integer, the minimum possible edge number in original graph. Output “impossible” if such graph doesn't exist.


Sample Input
3
3
0 1 1
1 0 1
1 1 0
3
0 1 3 
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0

Sample Output
Case 1: 6
Case 2: 4
Case 3: impossible

Source The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest
Recommend lcy | We have carefully selected several similar problems for you: 4039 4038 4036 4033 4037
題目大意:給出一個地圖,已知每兩個點之間的最短路徑,求原圖最少有多少條邊。 特別注意: 1、這個圖是有向圖。 2、可以找到原圖就是輸出最少有多少條邊,否則輸出-1。 3、用floyd找到最短路以及進行更新。 4、先得到邊,再通過floyd去掉一些邊,舉個例子說:1->2的最短路為5,2->3的最短路為3,1->3的最短路為12,很明顯1->2->3的<1->3的路徑,所以1->3這條邊可以去掉。 5、注意輸出有個Case,避免wa。
詳見代碼。
#include 
#include 
#include 
#include 

using namespace std;

int Map[110][110],n;

int Search()
{
    int flag=1;
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (i==j)
                continue;
            for (int k=1; k<=n; k++)
            {
                if (i==k&&j==k)
                    continue;
                if (Map[i][j]>Map[i][k]+Map[k][j]&&Map[i][k]&&Map[k][j])
                {
                    flag=0;
                    return -1;
                }
                else
                {
                    if (Map[i][j]==Map[i][k]+Map[k][j]&&Map[i][k]&&Map[k][j])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    return ans;
}

int main()
{
    int T;
    int nn;
    int Case=1;
    scanf(%d,&T);
    while (T--)
    {
        nn=0;
        scanf(%d,&n);
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                scanf(%d,&Map[i][j]);
                if (Map[i][j]!=0)
                    nn++;
            }
        }
        printf (Case %d: ,Case++);
        int cmp=Search();
        if (cmp==-1)
            printf (impossible
);
        else
            printf (%d
,nn-cmp);
    }
    return 0;
}



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved