| 圣诞岛的旅行 | 您所在的位置：网站首页 › 圣诞节点 › 圣诞岛的旅行 |
|
一道ACM上的题，无聊的时候写写。 圣诞岛的旅行 Problem Angel最近无聊，去了圣诞岛(CX *^_^*)，他喜欢无目的的乱逛，当然，他不会轻易地回头。Angel想去广场，那么，他什么时候才能到呢？你已经得到了CX的地图，地图上有N(N min) { distance[i][i + j].min = min; } } if (distance[i][k].max != MIN && distance[k][i + j].max != MIN) { int max = distance[i][k].max + distance[k][i + j].max; if (distance[i][i + j].max < max) { distance[i][i + j].max = max; } } } } } for (int j = 1; j < num; j++) { for (int i = 0; i + j < num; i++) { printf("[%d-%d]:min-%d;max-%d.\r\n", tpArray[i],tpArray[i + j], distance[i][i + j].min, distance[i][i + j].max); } } printf("%d\r\n%d\r\n", distance[tpArray[0]][tpArray[num - 1]].min, distance[tpArray[0]][tpArray[num - 1]].max); return 0; } int entry(int** graph, int* tpArray, int num) { if (topologicalSort(graph, tpArray, num)) { printf("图中存在环...end"); return -1; } merryIsland(graph, tpArray, num); return 0; } entry函数式解题主函数，先拓补排序，然后再按照拓步序列进行解题，需要注意的是拓步序列与实际图中点的对应关系下面是主函数和相关变量的初始化 #include #include #include #include "MerryIsland.h" int main() { int vn = 0; int en = 0; scanf_s("%d %d", &vn, &en); int** graph = new int*[vn]; for (int i = 0; i < vn; i++) { graph[i] = new int[vn]; memset(graph[i], 0, sizeof(int)*vn); } for (int i = 0; i < en; i++) { int s; int e; int l; scanf_s("%d %d %d", &s, &e, &l); graph[s][e] = l; } int* tpArray = new int[vn]; entry(graph, tpArray, vn); for (int i = 0; i < vn; i++) { printf("%d ", tpArray[i]); } system("pause"); return 0; }
|
| CopyRight 2018-2019 实验室设备网 版权所有 |