MZOJ #79 行动！行动！

分析

二维最短路板子题
嗯，dis[v][j] 可以由dis[u][j-1]或dis[u][i]转移过来
注意，如果用SPFA + SLF + swap，队列操作一定要判空！！！！
代码

  1 /**************************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:move
  5 Algorithm:
  6 **************************/
  7 
  8 #include<bits/stdc++.h>
  9 
 10 using namespace std;
 11 
 12 const int maxn = 1e4 + 5;
 13 const int maxm = 5e4 + 5;
 14 const int maxk = 13;
 15 
 16 int n,m,k,size,s,t;
 17 int first[maxn];
 18 int dis[maxn][maxk];
 19 bool vis[maxn][15];
 20 
 21 struct Node{
 22     int u,num,dis;
 23     Node(int _u = 0,int _dis = 0,int _num = 0):u(_u),dis(_dis),num(_num){}
 24     bool operator < (const Node &a) const {
 25         return dis > a.dis;
 26     }
 27 };
 28 
 29 struct Edge{
 30     int v,w,nt;
 31 }edge[maxm << 1];
 32 
 33 template<class T>inline void read(T &x){
 34     x = 0;bool flag = 0;char ch = getchar();
 35     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 36     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 37     if(flag) x = -x;
 38 }
 39 
 40 template<class T>void putch(const T x){
 41     if(x > 9) putch(x / 10);
 42     putchar(x % 10 | 48);
 43 }
 44 
 45 template<class T>void put(const T x){
 46     if(x < 0) putchar('-'),putch(-x);
 47     else putch(x);
 48 }
 49 
 50 void file(){
 51     freopen("move.in","r",stdin);
 52     freopen("move.out","w",stdout);
 53 }
 54 
 55 void eadd(int u,int v,int w){
 56     edge[ ++ size].v = v;
 57     edge[size].w = w;
 58     edge[size].nt = first[u];
 59     first[u] = size;
 60 }
 61 
 62 void readdata(){
 63     read(n);read(m);read(k);
 64     read(s);read(t);
 65     for(int i = 1;i <= m; ++ i){
 66         int u,v,w;
 67         read(u);read(v);read(w);
 68         eadd(u,v,w);
 69         eadd(v,u,w);
 70     }
 71 }
 72 
 73 void Dijkstra(){
 74     priority_queue<Node>q;
 75     memset(dis,0x3f3f3f3f,sizeof(dis));
 76     dis[s][0] = 0;
 77     q.push(Node(s,0,0));
 78     while(!q.empty()){
 79         Node x = q.top();
 80         q.pop();
 81         if(vis[x.u][x.num]) continue;
 82         vis[x.u][x.num] = 1;
 83         int u = x.u,num = x.num;
 84         for(int i = first[u];i;i = edge[i].nt){
 85             int v = edge[i].v;
 86             int w = edge[i].w;
 87             if(dis[v][num] > dis[u][num] + w){
 88                 dis[v][num] = dis[u][num] + w;
 89                 q.push(Node(v,dis[v][num],num));
 90             }
 91             if(num + 1 <= k && dis[v][num + 1] > dis[u][num]){
 92                 dis[v][num + 1] = dis[u][num];
 93                 q.push(Node(v,dis[v][num + 1],num + 1));
 94             }
 95         }
 96     }
 97 }
 98 
 99 void work(){
100     Dijkstra();
101     int ans = 2e9;
102     for(int i = 0;i <= k; ++ i) ans = min(ans,dis[t][i]);
103     //从0开始 
104     put(ans);
105 }
106 
107 int main(){
108 //    file();
109     readdata();
110     work();
111     return 0;
112 }
View Code
非做顽石不可，哪管他敬仰暗唾