【JLOI2011】飞行路线

题面

https://www.luogu.org/problem/P4568

题解

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,k,s,t,a,b,c;
vector<int> to[110500],l[110500];
int dis[110500];
bool vis[110500];
struct node{
  int t,d;
  bool operator < (const node rhs) const{
    return d>rhs.d;
  }
};
priority_queue<node> pq;

int main(){
  int i,j;
  node x;
  scanf("%d %d %d",&n,&m,&k);
  scanf("%d %d",&s,&t);
  for (i=1;i<=m;i++) {
    scanf("%d %d %d",&a,&b,&c);
    for (j=0;j<=k;j++) {
      to[n*j+a].push_back(n*j+b);
      l[n*j+a].push_back(c);
      to[n*j+b].push_back(n*j+a);
      l[n*j+b].push_back(c);
    }
    for (j=0;j<k;j++) {
      to[n*j+a].push_back(n*(j+1)+b);
      l[n*j+a].push_back(0);
      to[n*j+b].push_back(n*(j+1)+a);
      l[n*j+b].push_back(0);
    }
  }
  memset(dis,0x3f,sizeof(dis));
  dis[s]=0;
  pq.push((node){s,0});
  while (!pq.empty()) {
    x=pq.top(); pq.pop();
    if (vis[x.t]) continue;
    vis[x.t]=true;
    for (i=to[x.t].size()-1;i>=0;i--) 
      if (dis[x.t]+l[x.t][i]<dis[to[x.t][i]]) {
        dis[to[x.t][i]]=dis[x.t]+l[x.t][i];
        pq.push((node){to[x.t][i],dis[to[x.t][i]]});
      }
  }
  int ans=987654321;
  for (i=0;i<=k;i++) if (dis[t+i*n]<ans) ans=dis[t+i*n];
  printf("%d\n",ans);
  return 0;
}