Lutece 2222 cxx仙女下凡

题目链接: https://acm.uestc.edu.cn/problem/cxxxian-nu-xia-fan/description

分析:

因为路径不能与之前的相同,又要求最短,所以所求答案为第k短路。

k短路,其实也算个模板吧。

先以终点为源点跑一遍最短路,根据这个和边权给边排序。然后bfs,队列采取的是上面那个规则,就能跑出K短路了。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
const long long INF = 1LL << 60;

///////////////////////////
const long long MAXV=1501;
struct edge
{
    long long to,cost;
};
long long V,k;
vector<edge> G[MAXV];
vector<edge> G2[MAXV];
long long d[MAXV];
struct node
{
    long long to,cost;
    bool operator < (const node &a) const
    {
        return a.cost + d[a.to] < cost + d[to];
    }
};

void dijkstra(long long s)
{
    priority_queue< pair<long long,long long> , vector< pair<long long,long long> > ,greater< pair<long long,long long> > > q;
    fill(d,d+V+1,INF);
    d[s]=0;
    q.push( pair<long long,long long>(0,s) );
    while(!q.empty())
    {
        pair<long long,long long> p=q.top();
        q.pop();
        long long v=p.second;
        if(d[v]<p.first)
            continue;
        long long len=G[v].size();
        for(long long i=0;i<len;++i)
        {
            edge e=G[v][i];
            if(d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v] + e.cost;
                q.push(pair<long long,long long>(d[e.to],e.to));
            }
        }
    }
}

long long bfs(long long s,long long t)
{
    priority_queue<node> q;
    q.push((node){s,0});
    node n;
    long long len;
    while(!q.empty())
    {
        n=q.top();q.pop();
        if(n.to == t)
        {
            --k;
            if(k==0)
            {
                return n.cost;
            }
        }
        len = G2[n.to].size();
        for(long long i=0;i<len;++i)
        {
            q.push((node){G2[n.to][i].to,G2[n.to][i].cost+n.cost});
        }
    }
    return -1;
}
////////

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    long long m,u,v,w,s,t;
    cin>>V>>m>>k;
    cin>>s>>t;
    for(long long i=0;i<m;++i)
    {
        cin>>u>>v>>w;
        G2[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    dijkstra(t);
    if(d[s]==INF)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<bfs(s,t)<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注