道路翻新 (Revamping Trails, USACO 2009 Feb)

题意：给定m<=50000的1-n有联通的图，求最多可以使K<=20条边变为0的情况下的最短路是多少。。

思路：简单的分层图最短路，对于每个点拆成K个点。。

然后求一边最短路。。

code：

 /*
  * Author:  Yzcstc
  * Created Time:  2014/11/5 19:25:47
  * File Name: revamp.cpp
  */
 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<cstdlib>
 #include<cmath>
 #include<algorithm>
 #include<string>
 #include<map>
 #include<set>
 #include<vector>
 #include<queue>
 #include<stack>
 #include<ctime>
 #define M0(x)  memset(x, 0, sizeof(int) * (n+10))
 #define MP make_pair
 #define x first
 #define y second
 using namespace std;
 typedef long long ll;
 typedef pair<ll, int> pii;
 const int maxn = ;
 struct edge{
     int v, w, next;
 } e[maxn * ];
 int last[maxn], tot;
 int n, k, m; void add(const int &u,const int &v, const int& w){
      e[tot] = (edge){v, w, last[u]}; last[u] = tot++;
 } void init(){
      int u, v, w;
      memset(last, -, sizeof(int) * (n * k + ));
      tot = ;
      for (int i = ; i < m; ++i){
           scanf("%d%d%d", &u, &v, &w);
           add(u, v, w); add(v, u, w);
           for (int i = ; i <= k; ++i){
                add(u + i * n, v + i * n, w);
                add(v + i * n, u + i * n, w);
                add(u + (i-) * n, v + i * n, );
                add(v + (i-) * n, u + i * n, );
           }
      }
 } ll dis[maxn];
 int vis[maxn];
 void dij(){
      priority_queue<pii, vector<pii>, greater<pii> > q;
      int nt = n * k + n;
      memset(vis, , sizeof(vis));
      for (int i = ; i <= nt; ++i) dis[i] = (1LL<<);
      pii tmp(, ); dis[] = ;
      q.push(tmp);
      int u, v;
      while (!q.empty()){
           u = q.top().y;
           q.pop();
           if (vis[u]) continue;
           vis[u] = ;
           for (int p = last[u]; ~p; p = e[p].next){
                v = e[p].v;
                if (dis[u] + e[p].w < dis[v]){
                     dis[v] = dis[u] + e[p].w;
                     tmp.x = dis[v], tmp.y = v;
                     q.push(tmp);
                }
           }
      }
 } void solve(){
      dij();
      ll ans = 1LL<<;
      for (int i = ; i <= k; ++i)
         ans = min(ans, dis[n+i*n]);
      cout << ans << endl;
 } int main(){
     freopen("a.in", "r", stdin);
     freopen("a.out", "w", stdout);
     clock_t start, finish;
     start = clock();
     while (scanf("%d%d%d", &n, &m, &k) != EOF){
          init();
          solve();
     }
     finish = clock();
     double t = (double)(finish - start) / CLOCKS_PER_SEC;
 //    printf("time = %.6f\n", t);
     return ;
 }