Catalog
  1. 1. 一道分层图最短路的裸题
飞行路线-题解

查看原题请戳这里

一道分层图最短路的裸题

分层图最短路不会的戳这里 这道题实在是太裸了,我都不知道该在说写什么了(你把分层图最短路的版子交上去貌似都能过……) 附一下代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 2147483647

using namespace std;

struct node{
int k,dis,used;
bool operator < ( const node &x )const{return x.dis < dis;}
};

priority_queue<node> que;

long long n,m,k,s,t,d[50005],cnt,D[50005][15],v[50005][15];

struct Edge{
int to,next,x;
}edge[2000005];

void add(int x,int y,int a)
{
edge[++cnt].to = y;
edge[cnt].x = a;
edge[cnt].next = d[x];
d[x] = cnt;
}

int main()
{
int x,y,a;
scanf(“%lld%lld%lld”,&n,&m,&k);
scanf(“%d%d”,&s,&t);
s ++; t ++;
for(register int i = 1; i <= m; i++)
{
scanf(“%d%d%d”,&x,&y,&a);
x ++; y ++;
add(x,y,a);
add(y,x,a);
}
que.push((node){s,0,0});
for(register int i = 0; i <= n; i++)
for(register int j = 0; j <= k; j++)
D[i][j] = INF;
D[s][0] = 0;
while(!que.empty())
{
node u = que.top();
que.pop();
int kk = u.k,level = u.used;
if(v[u.k][u.used]) continue;
v[u.k][u.used] = 1;
for(register int i = d[kk]; i; i = edge[i].next)
{

        int too = edge[i].to;
        if(D[too][level] &gt; D[kk][level] + edge[i].x)
        {
            D[too][level] = edge[i].x + D[kk][level];
            que.push((node){too,D[too][level],level});
        }
        if(level &lt; k &amp;&amp; D[too][level + 1] &gt; D[kk][level])
        {
            D[too][level + 1] = D[kk][level];
            que.push((node){too,D[too][level + 1],level + 1});
        }
    }
}
long long  ans = INF;
for(register int i = 0; i &lt;= k; i++) ans = min(ans,D[t][i]);
printf("%lld\n",ans);
return 0;

}

Author: wflight
Link: http://yoursite.com/2019/08/02/飞行路线-题解/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment