首页 > 代码库 > zoj 1221

zoj 1221

2024-07-06 18:00:52   232人阅读

先解释一下题目的意思，看了我好久。。。;英语不好又不仔细看的人真心伤不起。。。。。

输入19行表示的是 第 i 行就是第 i 个数字相邻的城市的个数的多少，然后输入相邻的城市，只算比 i 大的数，小的就不算了

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1221

解释一下dijkstra 和 flody 区别 

dijkstra 是不能有负数边的，因为他每次加入都是目前最小权值的边和对应的 结点，如果有负数边，可能再下一次再加另一个结点之后，该结点到原先已经加入的结点的边为负数，则会导致原来的算法不正确。因为如果已经访问过的结点，就默认已经找到最小路径了，而实际上是可能通过一条负数边而使他的路径变得更小的。

FLODY 算法则因为是所有都要遍历过，就是通过一个结点，两个结点，直到n-1个结点。。每次只留下最短的，最后一次性得到到所有结点的最小路径，因此可以有负数边。

个人拙见。。。

 

都现在都有点理不清最短路径和最小生成树的那些算法，等有时间了一定要好好理清一下。。。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 1221.cpp : Defines the entry point for the console application.
//好像没有必要用floyd的感觉。。。。。试一下吧
 
//#include "stdafx.h"
#include <iostream>
#include <memory>
using namespace std;
 
int A[21][21];//存边的数组
 
int max = 9;//最大值 路不通
 
int main()
{
    int data, sum, from, to, n, start = 1;
 
    //memset(A, max, sizeof(A));
    while (~scanf("%d", &sum))//当前结点相邻边的个数
    {
        for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= 20; j++)
            A[i][j] = 9;
        while (sum--)
        {
            scanf("%d", &data);
            A[data][1] = A[1][data] = 1;//表示通路，可以到达
        }
        for (int i = 2; i < 20; i++)//输入19行数据
        {
            A[i][i] = 0;//访问标志
            scanf("%d", &sum);
            while (sum--)
            {
                scanf("%d", &data);
                A[data][i] = A[i][data] = 1;//表示通路，可以到达
            }
        }
//      for (int i = 1; i <= 20; i++)
//      for (int j = 1; j <= 20; j++)
//      {
//          cout << A[i][j] << "  ";
//          if (j == 20)
//              cout << endl;
//      }
        for (int k = 1; k <= 20; k++)
        for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= 20; j++)     //一次Folyd算法记录所有点间的最短路径
        if (A[i][j] > A[i][k] + A[k][j])
            A[i][j] = A[i][k] + A[k][j];
 
        scanf("%d", &n);
        printf("Test Set #%d\n", start++);
        while (n--)
        {
            scanf("%d%d", &from, &to);
            printf("%d to %d: %d\n", from, to, A[from][to]);
        }
        printf("\n");
    }
 
 
    return 0;
}

 

 


联系
我们