分层最短路-2018南京网赛L

大概题意：

题意：N个点，M条带权有向边，求将K条边权值变为0的情况下，从点1到点N的最短路。

拓展：可以改变K条边的权值为x

做法：把每个点拆成k个点，分别表示还能使用多少次机会，构造新图。

实际写的时候，不用真的拆点，用dist[i][j]表示从源点出发到点i，免费j条边的最小花费，在dijkstra中维护分层即可，每个节点要存价值，编号，已经用的免费条数。

 #include <iostream>

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int maxm = ;  //±ß

 const int maxn = ; //µã

 const int inf = 0x3f3f3f3f;

 struct Edge

 {

     int to,v,next;

 } edge[maxm];

 struct node

 {

     long long val;

     int num, h;

     node(long long _val=, int _num=, int _d=):val(_val), num(_num),h(_d) {}

     bool operator <(const node &tmp) const

     {

         return val > tmp.val;

     }

 };

 int head[maxn];

 int top;

 int N, M, K;

 long long dis[maxn][];

 bool vis[maxn][];

 long long ans = inf;

 void init()

 {

     memset(head, -, sizeof(head));

     top = ;

     for(int i=; i<=N; i++)

     {

         for(int j=; j<=K; j++)

         {

             dis[i][j] = inf;

             vis[i][j] = false;

         }

     }

     ans = inf;

 }

 void addedge(int from, int to, int v)

 {

     edge[top].to = to;

     edge[top].v = v;

     edge[top].next = head[from];

     head[from] = top++;

 }

 void dijkstra()

 {

     priority_queue<node> que;

     dis[][] = ;

     que.push(node(, , ));

     while(!que.empty())

     {

         node p = que.top();

         que.pop();

         int nown = p.num;

         int h = p.h;

         if(vis[nown][h])

             continue;

         vis[nown][h] = true;

         for(int i=head[nown]; i!=-; i=edge[i].next)

         {

             Edge e = edge[i];

             if(dis[e.to][h] > dis[nown][h] + e.v)

             {

                 dis[e.to][h] = dis[nown][h] + e.v;

                 que.push(node(dis[e.to][h], e.to, h));

             }

             //修改的地方

             if(dis[e.to][h+] > dis[nown][h] && h < K)

             {

                 dis[e.to][h+] = dis[nown][h];

                 que.push(node(dis[nown][h], e.to, h+));

             }

         }

     }

     for(int i=; i<=K; i++)

     {

         ans = min(ans, dis[N][i]);

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d", &N, &M, &K);

         init();

         int u, v, c;

         for(int i=; i<M; i++)

         {

             scanf("%d%d%d", &u, &v, &c);

             addedge(u, v, c);

         }

         dijkstra();

         printf("%lld\n", ans);

     }

     return ;

 }