[PA 2012 final]Tax

先備知識：dijkstra求最短路

這題怎麼用dijkstra呢？
題目說，經過每個城鎮都要收費，因此我們試著把城鎮當邊，那路就是點啦！

實作上可以先把連接城鎮1的所有路push進priority_queue裡面，注意，這裡的路要轉成有向的，因此會有$2M$個點，相信大家都知道一個點可以走到哪些其他點，dijkstra的過程就不細講了XD，最後，當發現一個點代表的路的起點是城鎮N的話，就可以直接回傳答案了 (想一想，為甚麼XD)

範測對了，傳上去......TLE, TLE, TLE,......

注意，圖上的點數$=M$，那邊數呢？和同一個城鎮連多少條路成平方比率增加！

因此，我們必須做一些優化：
對於每個城鎮，將它連接的路依照權重排序，這樣要從「進城的路」照路的收費依序考慮每一條「出城的路」，當走一條路的收費已經無法比先前的最優解還低時，可以直接break跳出迴圈
至於這樣為甚麼答案還是對的，個人覺得滿顯然，仔細模擬應該可以找出為甚麼XD

還有很奇怪的一點，這樣的優化應該不會影響時間複雜度，可是卻會造成$>10$秒的TLE和$<1$秒的AC之間的差別！

時間複雜度：$O(M+N^{2}\log N)$(優化萬歲！XD)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
void getmin(LL &a,const LL &b){if(b<a)a=b;}
struct Edge
{
    int a,b;
    LL cost;
    Edge(){}
    Edge(const int _a,const int _b,const LL &_cost):a(_a),b(_b),cost(_cost){}
};
vector<Edge>EDGE;
struct Pq
{
    int ei;
    LL cost;
    Pq():ei(),cost(){}
    Pq(const int _ei,const LL &_cost):ei(_ei),cost(_cost){}
    bool operator<(const Pq &p)const{return cost>p.cost;}
};
int N,M;
vector<int>ET[100000];
bool CmpEdgeIdx(const int a,const int b){return EDGE[a].cost!=EDGE[b].cost?EDGE[a].cost<EDGE[b].cost:a<b;}
LL Solve()
{
    static bool vis[400000];
    static LL dist[400000];
    for(int i=0;i<M*2;i++)vis[i]=false,dist[i]=INF;
    priority_queue<Pq>pq;
    for(int i=0;i<(int)ET[0].size();i++)pq.push(Pq(ET[0][i],EDGE[ET[0][i]].cost));
    while(!pq.empty())
    {
        const Pq p=pq.top();pq.pop();
        if(vis[p.ei])continue;
        vis[p.ei]=true;
        const Edge &e=EDGE[p.ei];
        if(e.a==N-1)return p.cost;
        for(int i=0;i<(int)ET[e.b].size();i++)
        {
            const int ei=ET[e.b][i];
            const Edge &nxte=EDGE[ei];
            const LL cost=p.cost+max(e.cost,nxte.cost);
            if(cost>=dist[ei])break;
            dist[ei]=cost;
            pq.push(Pq(ei,cost));
        }
    }
    assert(0);return -1LL;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        EDGE.clear();
        for(int i=0,a,b,c;i<M;i++)
        {
            scanf("%d%d%d",&a,&b,&c),a--,b--;
            EDGE.push_back(Edge(a,b,c));
            EDGE.push_back(Edge(b,a,c));
            ET[a].push_back(i*2),ET[b].push_back(i*2+1);
        }
        for(int i=0;i<N;i++)sort(ET[i].begin(),ET[i].end(),CmpEdgeIdx);
        printf("%lld\n",Solve());
    }
    return 0;
}