本文共 1905 字，大约阅读时间需要 6 分钟。

题目大意：两个小屁孩要乘飞机去旅行。现在给一些无向边和边权，另外他们还有K次免费乘坐飞机的机会，问从起点到终点的最小话费是什么。

思路：分层图第一题。之前听到分层图还以为是真的建K个图，然后不同层数之间的点连边跑最短路。。后来经同学讲解才发现我想多了。。

其实还是动归的思想（最短路不也是动归的思想么(｀・ω・´)），f[ i ][ j ]表示在j位置时，已经用了i次免费机会的时候的最小花费，然后在SPFA里多一维的转移就可以了。

PS：BZOJ上这个题还是挺卡常数的，我之前用queue用了9388ms险些T，改用priority_queue之后时间一下子到了276ms。。-O2的力量。。

CODE：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAX 100000#define INF 0x7f7f7f7fusing namespace std;int f[11][MAX];struct Complex{	int pos,step;	Complex(int _step,int _pos):pos(_pos),step(_step) {}	Complex() {}	bool operator <(const Complex &a)const {		return f[step][pos] > f[a.step][a.pos];	}}; int points,edges,steps; int start,end;bool v[11][MAX];int head[MAX],total;int next[MAX],aim[MAX],length[MAX]; inline void Add(int x,int y,int len);void SPFA(); int main(){    cin >> points >> edges >> steps;    cin >> start >> end;    start++,end++;    for(int x,y,z,i = 1;i <= edges; ++i) {        scanf("%d%d%d",&x,&y,&z); x++,y++;        Add(x,y,z),Add(y,x,z);    }    SPFA();    int ans = INF;    for(int i = 0;i <= steps; ++i)        ans = min(ans,f[i][end]);    cout << ans;    return 0;} inline void Add(int x,int y,int len){    next[++total] = head[x];    aim[total] = y;    length[total] = len;    head[x] = total;} void SPFA(){    static priority_queue
        
          q; memset(f,0x3f,sizeof(f)); q.push(Complex(0,start)); f[0][start] = 0; while(!q.empty()) { Complex temp = q.top(); q.pop(); int x = temp.pos,step = temp.step; v[step][x] = false; for(int i = head[x];i;i = next[i]) { if(f[step][aim[i]] > f[step][x] + length[i]) { f[step][aim[i]] = f[step][x] + length[i]; if(!v[step][aim[i]]) { v[step][aim[i]] = true; q.push(Complex(step,aim[i])); } } if(f[step + 1][aim[i]] > f[step][x] && step < steps) { f[step + 1][aim[i]] = f[step][x]; if(!v[step + 1][aim[i]]) { v[step + 1][aim[i]] = true; q.push(Complex(step + 1,aim[i])); } } } }}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/39180645 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！