[TIOJ] 1530 皮皮歷險記--魔尊皮皮

LINK：https://tioj.infor.org/problems/1530
　　我看了別人的code才會的orz
　　簡單來說，這題要求一條等級嚴格遞增且使的時間耗費最少的從s到e的路徑，由於等級嚴格遞增，所以假設我們先將邊以等級排序，然後從最小的開始取，若其兩端點分別為x,y，則可以證明若經由邊可以鬆弛某條路徑的話，則其終點肯定在x或y上，事實上是因為我們將邊排序了，所以現在取出來的邊是目前已經有的中等級最大的那個，而不可能以這條邊再接出去了，所以這條邊一定是終邊。
　　特別注意的是等級相同的邊，由於互相不能互通，所以處理時必須一併處理才可以。

#include<bits/stdc++.h>
#define int long long
#define pi pair<pair<int,int>,pair<int,int> >
#define F first
#define S second
#define INF 1e16
#define getchar getchar_unlocked
#define putchar putchar_unlocked

inline void output(int _x)
{
    char _buff[20]; int _f = 0;
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
inline void input(int &_x)
{
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
using namespace std;
int n,m,s,e;
vector<pi> hey;
int d[500009],d2[500009];
vector<pi> hello;
main()
{
    input(n); input(m); input(s); input(e);
    fill(d+1,d+n+1,INF);
    while(m--)
    {
        int a,b,c,dd; input(a); input(b);input(c); input(dd);
        hello.push_back({{dd,c},{a,b}});
    }
    sort(hello.begin(),hello.end());
    d[s] = 0;
    for(int t = 0; t < hello.size(); t++)
    {
        d2[hello[t].second.first] = d2[hello[t].second.second] = INF;
        hey.clear(); hey.push_back(hello[t]);
        while((t+1) != hello.size() && hello[t+1].first.first == hello[t].first.first) 
        {
            d2[hello[t+1].second.first] = d2[hello[t+1].second.second] = INF;
            hey.push_back(hello[t+1]), t++;
        }
        for(auto i:hey)
        {
            d2[i.second.first] = min(d2[i.second.first],min(d[i.second.first],d[i.second.second]+i.first.second));
            d2[i.second.second] = min(d2[i.second.second],min(d[i.second.second],d[i.second.first]+i.first.second));
        }
        for(auto i:hey) 
        {
            d[i.second.first] = min(d[i.second.first],d2[i.second.first]);
            d[i.second.second] = min(d[i.second.second],d2[i.second.second]);
        }
    }
    if(d[e] >= 1e15+10) puts("Pipi how way!!!");
    else output(d[e]);
}