Telephone Line S

题目大意:

首先你有一张图，问你从到的路径中第条最大的边最小有多大

分析：

这个题很显然是可以二分答案的
但是我们考虑换一种做法：分层图
那么就是跨层的时候让其代价为，那么一共就有层图
在跑一个类似最短路的东西就可以了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x7f7f7f7f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, p, k, cur;
int head[maxn], edge[maxn], __prev[maxn], cost[maxn];

inline void _addedge(int u, int v, int w)
{
    __prev[++cur] = head[u];
    head[u] = cur;
    edge[cur] = v;
    cost[cur] = w;
}

inline void __addedge(int u, int v, int w)
{
    _addedge(u, v, w), _addedge(v, u, w);
}

int dis[maxn];
bool vis[maxn];
inline void SPFA()
{
    memset (dis, 0x7f, sizeof dis);
    deque <int> Q;
    Q.push_back(1);
    dis[1] = 0;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop_front();
        vis[now] = 0;
        for (int i = head[now]; i; i = __prev[i]) {
            const int v = edge[i];
            if (dis[v] <= max(dis[now], cost[i])) continue;
            dis[v] = max(dis[now], cost[i]);
            if (vis[v]) continue;
            if (Q.empty() || dis[v] <= dis[Q.front()]) Q.push_front(v);
            else Q.push_back(v);
            vis[v] = 1;
        }
    }
    if (dis[n * (k + 1)] == inf) puts("-1");
    else printf ("%d\n", dis[n * (k + 1)]);
}

int main()
{
    n = __read(), p = __read(), k = __read();
    while (p--) {
        int u = __read(), v = __read(), a = __read();
        __addedge(u, v, a);
        for (int i = 1; i <= k; ++i) {
            __addedge(i * n + u, i * n + v, a);
            _addedge((i - 1) * n + u, i * n + v, 0);
            _addedge((i - 1) * n + v, i * n + u, 0);
        }
    }
    SPFA();
    system("pause");
}