题目

思路

• 利用SPFA避免重复入队，适用于边数特别大的BF
• 利用层数控制边数K的限制

//spfa实现bf
#include<bits/stdc++.h>
using namespace std;
const int N=510,M=1e4+10;
int h[N],e[M],ne[M],w[M],idx;
int n,m,k;
int dist[N],last[N];
bool st[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa(){
    int cnt=0;
    memset(dist,0x3f,sizeof dist);
    deque<int> que;
    dist[1]=0;
    que.push_back(1);
    //维护层数以维护边数限制
    while(!que.empty()){
        int sz=(int)que.size();
        for(int i=1;i<=n;i++) st[i]=false,last[i]=dist[i];
        while(sz--){
            int t=que.front();
            que.pop_front();
            for(int i=h[t];~i;i=ne[i]){
                int j=e[i];
                if(dist[j]>last[t]+w[i]){
                    dist[j]=last[t]+w[i];
                    if(!st[j]){
                        que.emplace_back(j);
                        st[j]=true;//避免反复入队
                    }
                }
            }
        }
        cnt++;
        if(cnt>=k) return;
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    if(dist[n]>=0x3f3f3f3f/2) puts("impossible");
    else cout<<dist[n];
}