地铁 Dijkstra(优先队列优化) 湖南省第12届省赛

时间：2023-03-08 17:39:55

传送门：地铁

思路：拆点，最短路；拆点比较复杂，所以对边进行最短路，spfa会tle，所以改用Dijkstra(优先队列优化)

模板

/**************************************************************

    Problem:

    User: youmi

    Language: C++

    Result: Accepted

    Time:

    Memory:

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo (1e16)

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    if (n == ) return ;

    if (n == ) return base % mo;

    ll tmp = Pow(base, n >> , mo);

    tmp = (ll)tmp * tmp % mo;

    if (n & ) tmp = (ll)tmp * base % mo;

    return tmp;

}

//***************************

int n,m;

const int maxn=+;

const ll mod=;

struct node

{

    int v,c;

    ll t,dis;

    node(){}

    node(int _v,int _c,ll _t,ll _dis)

    {

        v=_v,c=_c,t=_t,dis=_dis;

    }

    bool operator<(const node &a)const

    {

        if(dis==a.dis)

            return t>a.t;

        return dis>a.dis;

    }

};

vector<node>vt[maxn];

void dijkstra()

{

    ll ans=oo;

    priority_queue<node>q;

    for(int i=;i<vt[].size();i++)

    {

        vt[][i].dis=vt[][i].t;

        if(vt[][i].v==n)

            ans=min(ans,vt[][i].dis);

        q.push(vt[][i]);

    }

    while(!q.empty())

    {

        node cur=q.top();

        q.pop();

        for(int i=;i<vt[cur.v].size();i++)

        {

            node temp=vt[cur.v][i];

            if(temp.dis>cur.dis+temp.t+abs(cur.c-temp.c))

            {

                temp.dis=cur.dis+temp.t+abs(cur.c-temp.c);

                if(temp.v==n)

                    ans=min(ans,temp.dis);

                vt[cur.v][i]=temp;//非常重要，不要忘了这一步

                q.push(temp);

            }

        }

    }

    printf("%lld\n",ans);

}

int main()

{

    #ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

    #endif

    while(~sc2(n,m))

    {

        int a,b,c;

        ll t;

        for(int i=;i<=n;i++)

            vt[i].clear();

        rep(i,,m)

        {

            sc3(a,b,c);

            scanf("%lld",&t);

            vt[a].push_back(node(b,c,t,oo));

            vt[b].push_back(node(a,c,t,oo));

        }

        dijkstra();

    }

}