ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze(dijkstra+分层图)

​
#include <bits/stdc++.h>
#define maxn 401000*11
#define ll long long
using namespace std;
struct node{
  ll next;
  ll to;
  ll val;
}Edge[maxn];
struct Node{
  ll val;
  ll cnt;
  bool operator < (const Node &a) const {
    if(a.val == val) return a.cnt < cnt;
    return a.val < val;
  }
}Next,Now;
ll n,m,k;
ll head[maxn],num,dist[maxn];
bool vis[maxn];
priority_queue<Node> q;

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
}

void add(ll u,ll v,ll val){
  Edge[num].to = v;
  Edge[num].val = val;
  Edge[num].next = head[u];
  head[u] = num++;
}

void dijkstra(){
  memset(vis,false,sizeof(vis));
  memset(dist,0x3f3f3f3f,sizeof(dist));
  Now.val = 0;
  Now.cnt = 1;
  dist[1] = 0;
  q.push(Now);
  while(!q.empty()){
    Now = q.top();
    q.pop();
    ll flag = Now.cnt;
    if(vis[flag])continue;
    vis[flag] = true;
    for(ll i=head[flag]; i != -1; i = Edge[i].next){
      ll u = Edge[i].to;
	  if(!vis[u] && dist[u] > dist[flag] + Edge[i].val){
		dist[u] = dist[flag] + Edge[i].val;
		Next.cnt = u;
		Next.val = dist[u];
		q.push(Next);
	  }
    }
  }
  ll ans = 0x3f3f3f3f;
  for(int i=0;i<=k;i++){
    ans = min(ans, dist[n + i * n]);
  }
  printf("%lld\n",ans);
}

int main()
{
  int T;
  scanf("%d",&T);
  while(T--){
    init();
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=0;i<m;i++){
      ll u,v,w;
      scanf("%lld%lld%lld",&u,&v,&w);
      for(int j=0;j<=k;j++){
        add(u+j*n, v+j*n, w);
        // add(v+j*n, u+j*n, w);
        if(j != k){
          add(u+j*n, v+(j+1)*n, 0);
          // add(v+j*n, u+(j+1)*n, 0);
        }
      }
    }
    dijkstra();
  }
  return 0;
}

​