2402

#if 1
//   1. PQ 방식 
//
//   * 최소중 최대 찾기 
//    --> 갈수 있는 path 에서 최소 중량의 간선이  최대인 값 확인 
//    . DFS/BFS/PQ 방식등 여러가지 방법중   PQ 를 사용하는 방법이 가장 빠르다.
//  PQ 를 사용하는 방법은 
//  현재 도시에서 항상 최대 중량의 간선을 선택하여 진행한다. 이 때 선정대상의 간선은 현재까지 선정된 도시와 연결된 모든 간선들 중에 
//  가장 중량이 큰 간선이고   PQ 들어갈  {중량, to_city} 에서 중량은 현재까지 최소 중량의 간선이다. 
//  이렇게 하면   시작도시에 도착도시까지 전체  path 를 확인하지 않고  처음 도착한   PQ의 중량정보가  갈 수 있는 최대 중량 정보이다. 
//  여기서 중요한 것이  visit 배열인데  ... 2차원 배열 visit[fm_city][to_city] 로 해야 이후에 도착하는 중량이 큰 간선정보를 받아들일 수 있다. 
//
//   손코딩 PQ  를 적용하면 더 빠른 결과를 얻을 수 있다. (현 문제에서는  3배정도)
//
 
#include <vector>
#include <algorithm>
#define rint register int
using namespace std;
 
// 손코딩 PQ 
// index-1 base & swap 최소화하는 코드인데  이해하고 외워야한다. 
// 여러분은  이코드를 사용하지 말고 러퍼런스 코드를 copy 하여 응용하시면 됩니다. 
//
const int MAX_HEAP = 10000;
template <typename T>
struct priority_queue
{
    T heap[MAX_HEAP];
    int sz;
    void clear() { sz = 0; }
    bool empty() { return sz == 0; }
    void push(T val)
    {
        rint c = ++sz; // child
        for( ; c >1 && val > heap[c/2] ; c >>=1) heap[c] = heap[c>>1];
        heap[c] = val;
    }
    T top() { return heap[1]; }
    void pop()
    {
        T val = heap[sz--];
        rint c = 2;
        for (; c <= sz; c <<= 1)
        {
            if (c + 1 <= sz && heap[c + 1] > heap[c]) c++; // 자식중 작은 자식 선정
            if (val > heap[c])  break;
            heap[c>>1] = heap[c];
        }
        heap[c >>1] = val;
    }
};
 
vector<pair<int, int>> Edge[1010]; // 간선 정보 < weight, to_city> 
 
void init(int N, int K, int sCity[], int eCity[], int mLimit[]) {
    for (rint i = 0; i < N; ++i)Edge[i].clear();
    for (rint i = 0; i < K; ++i)
    {
        Edge[sCity[i]].push_back({ mLimit[i],eCity[i] });
    }
}
 
void add(int sCity, int eCity, int mLimit)
{
    Edge[sCity].push_back({ mLimit,eCity }); // 간선 정보추가
}
 
priority_queue< pair<int, int>> pq; // weight , city
 
int visit[1001][1001];
int vc;
int calculate(int sCity, int eCity) {
    vc++;
    pq.clear();
    pq.push({ 100000,sCity });  // 시작 도시 설정 ,  max 중량:30,000 보다큰 수 설정 
    while (!pq.empty())
    {
        register auto it = pq.top(); pq.pop();
        if (it.second == eCity) { // 목적지 도달
            return it.first; // 옮길 수 있는 최대 중량 
        }
        for ( auto to : Edge[it.second]) // it.second city 에서 갈 수 있는 간선 정보 
        {
            if (visit[it.second][to.second] != vc) // from --> to city 로 간 이력이 있는 정보는 제외
            {
                visit[it.second][to.second] = vc;
                int weight = min(it.first, to.first); // 계속 최소 중량으로 update 한다. 
                pq.push({ weight,to.second });
            }
        }
    }
    return -1;
}
#endif // 0
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// BFS 방식 : 0.323Sec 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if 0
//
// BFS 방식 모든 가능한  path 를 다 만들고 그중 가장 weight 가 작은것 중에 가장 큰것을 선택한다. 
// 중간에   weight 가   max_weight  보다 작은  path  들은 가지 치기 한다. 
//
//  Queue 손코딩이 중요하네요  ( 0.323sec)  
//  PQ 보다 좀 느리네요 
//  
#include <vector>
#include <algorithm>
//#include <queue>
#define rint register int
using namespace std;
#if 1
 
template <typename T>
struct queue
{
    T Q[1000000];
    int rp, wp;
    void clear() { rp = wp = 0; }
    bool empty() { return rp == wp; }
    void push(T val) { Q[++wp] = val; }
    T front() { return Q[rp + 1]; }
    void pop() { ++rp; }
};
 
 
#endif // 0
vector<pair<int, int>> Edge[1010]; // 간선 정보 < weight, to_city> 
 
int N;
 
 
void init(int N, int K, int sCity[], int eCity[], int mLimit[]) {
    ::N = N;
    for (rint i = 0; i < N; ++i)Edge[i].clear();
    for (rint i = 0; i < K; ++i)
    {
        Edge[sCity[i]].push_back({ mLimit[i],eCity[i] });
    }
}
 
void add(int sCity, int eCity, int mLimit)
{
    Edge[sCity].push_back({ mLimit,eCity });
}
 
queue< pair<int, int>> que; // weight , city
int max_weight;
int calculate(int sCity, int eCity) {
    int vw[1001] = { 0, }; // idx city 에 방문한 현재 최대 중량 
    max_weight = -1;
    que.clear(); 
    //que = {};
    que.push({ 100000,sCity });  // max :30,000
    while (!que.empty())
    {
        auto it = que.front(); que.pop();
        if (it.first <= max_weight) continue;
        if (it.second == eCity)
        {
            max_weight = max(max_weight, it.first); // it.first 현재  path 중  최소 간선의 중량 
            continue;
        }
        for (auto to : Edge[it.second]) // it.second city 에서 갈 수 있는 간선 정보 
        {
            int weight = min(it.first, to.first);
            if (vw[to.second] < weight) // 현재 city  방문한 weigth 보다 큰 weigth path  만 방문하면 된다. 
            {
                vw[to.second] = weight;
                que.push({ weight,to.second });
            }
        }
    }
    return max_weight;
}
#endif // 0