201703-4 试题名称： 地铁修建

题目链接：201703-4 试题名称： 地铁修建

题意：

给出两点之间需要施工的天数，每条路径可以同时施工，求1到N最少需要几天。

分析

求最短路径dijkstra的改编，因为数据较大，需要使用小根堆的数据结构，可以使用stl的优先队列，使花费少的放在第一个。因为施工是同时进行的，所以1到i的最小天数为其路径上最大的天数。选择到达i的最佳邻接点为最短的，即当原dis[i] 大于 u 到 i的距离时，dis[i]的距离等于u到i的距离和dis[u]的距离中最大值。例如 2 -> 3距离为5,1->3距离为4，dis[2] = 3, dis[1] = 4, 所以dis[3] = max(dis[1], 4); 每次更新距离后，将节点x,dis[x]加入队列。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 100010;
const int INF = 99999989;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int book[maxn] = {
    0}, dis[maxn];
int n, m;
typedef struct Node {
    int x, c;Node() {
    };Node(int tx, int tc) {
    x = tx;c = tc;}friend bool operator < (Node n1, Node n2) {
    return n1.c > n2.c;}
}Node;
vector<Node> v[maxn];
void dij() {
    priority_queue<Node> que;que.push(Node(1, 0));for (int k = 0; k < n; k++) {
    while(!que.empty() && book[que.top().x] != 0)que.pop();int u = -1;if (!que.empty()) {
     // 得到最小值u = que.top().x;que.pop();}book[u] = 1;for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i].x;if (book[x] == 0 && dis[x] > v[u][i].c) {
    
// printf(" u = %d x = %d, dis = %d\n", u, x, dis[u]);dis[x] = max(v[u][i].c, dis[u]); // dis[x]为u->x的费用，和到u的费用最大值。即路径上的最大值
// printf("dis[x] = %d\n", v[u][i].c);que.push(Node(x, dis[x]));}}}
}
/** 5 6 1 2 1 1 3 2 1 4 1 2 3 1 3 5 1 4 5 1 */
int main(int argc, char** argv) {
    int x, y, c;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &x, &y, &c);v[x].push_back(Node(y, c));v[y].push_back(Node(x, c));}fill(dis + 1, dis + n + 1, INF);dis[1] = 1;dij();printf("%d", dis[n]);return 0;
}