图片说明

  • 题意：
  • 给出一个无向图有n个点和m条边，问你从1走到n，可以至多将k条路的长度变为0，问你最短路的长度
  • 题解：
  • 分层最短路
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 400000*11;
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);
              if(j != k){
                  add(u+j*n,v+(j+1)*n,0);
              }
          }
      }
      dijkstra();
  }
  return 0;
}

```