首页 > 代码库 > zoj 1221
zoj 1221
先解释一下题目的意思,看了我好久。。。;英语不好又不仔细看的人真心伤不起。。。。。
输入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; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。