AC日记——魔法森林 洛谷 P2387

魔法森林

 

思路：

　　spfa水过(正解lct);

 

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 50005
#define maxm 200005
#define INF 0x3f3f3f3f
struct RoadType {
    int u,v,ai,bi;
    bool operator<(const RoadType pos)const
    {
        if(ai==pos.ai) return bi<pos.bi;
        return ai<pos.ai;
    }
};
struct RoadType road[maxm];
int n,m,head[maxn],E[maxm],V[maxm],W[maxm],ans(INF);
int dis[maxn],cnt;
bool vis[maxn];
queue<int>que;
inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0')Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}
inline void edge_add(int u,int v,int w)
{
    E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,head[u]=cnt;
    E[++cnt]=head[v],V[cnt]=u,W[cnt]=w,head[v]=cnt;
}
int main()
{
    in(n),in(m);
    for(int i=1;i<=m;i++)
    {
        in(road[i].u);
        in(road[i].v);
        in(road[i].ai);
        in(road[i].bi);
    }
    for(int i=2;i<=n;i++) dis[i]=INF;
    sort(road+1,road+m+1);
    for(int i=1;i<=m;i++)
    {
        if(road[i].u==road[i].v) continue;
        edge_add(road[i].u,road[i].v,road[i].bi);
        if(!vis[road[i].u]) que.push(road[i].u),vis[road[i].u]=true;
        if(!vis[road[i].v]) que.push(road[i].v),vis[road[i].v]=true;
        if(road[i].ai==road[i-1].ai&&road[i].bi==road[i-1].bi) continue;
        while(!que.empty())
        {
            int now=que.front();que.pop(),vis[now]=false;
            for(int i=head[now];i;i=E[i])
            {
                if(dis[V[i]]>max(dis[now],W[i]))
                {
                    dis[V[i]]=max(dis[now],W[i]);
                    if(!vis[V[i]])
                    {
                        vis[V[i]]=true;
                        que.push(V[i]);
                    }
                }
            }
        }
        if(ans>road[i].ai+dis[n]) ans=road[i].ai+dis[n];
    }
    printf("%d\n",ans==INF?-1:ans);
    return 0;
}