第一版 err
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define N 505
using namespace std;
int n,m,k,dis[N],cnt,hd[N],vis[N],x,y,z;
struct Edge{
int to, nxt, w;
}edge[10005];
struct Node{
int c,d;
}node[N];
queue<Node> q;
void add(int u, int v, int w){
edge[++cnt].to = v;
edge[cnt].nxt = hd[u];
edge[cnt].w = w;
hd[u] = cnt;
}
void spfa(){//
q.push((Node){1,0}); dis[1] = 0; vis[1] = 1;
while(!q.empty()){
Node t = q.front(); q.pop();
int u = t.c; vis[u] = 0;
if(t.d == k) return;
for(int i = hd[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(dis[u] + edge[i].w < dis[v]){
dis[v] = dis[u] + edge[i].w;
if(!vis[v]){
vis[v] = 1;
q.push((Node){v, t.d+1});
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= m; i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
memset(dis, 0x3f, sizeof dis);
spfa();
if(dis[n] >= 0x3f3f3f3f/2) printf("impossible\n");
else printf("%d\n",dis[n]);
return 0;
}
/* 1-2-3-4 \ | 5 | \ / 6 入队： 1 5 2 6 3 （6出队的时候，将3更新，但3已经在队中，那么3到底是第3层还是第4层，3出队的时候如何更新4？） */
bellman-ford过程第三遍更新时，3会被更新，4也会被更新，这样4相当于是1-5-6-3-4，而不是1-2-3-4
第二版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define N 505
using namespace std;
int n,m,k,dis[N][10005],cnt,hd[N],vis[N][10005],x,y,z;
struct Edge{
int to, nxt, w;
}edge[10005];
struct Node{
int c,d;
}node[N];
queue<Node> q;
void add(int u, int v, int w){
edge[++cnt].to = v;
edge[cnt].nxt = hd[u];
edge[cnt].w = w;
hd[u] = cnt;
}
void spfa(){//
q.push((Node){1,0}); dis[1][0] = 0; vis[1][0] = 1;
while(!q.empty()){
Node t = q.front(); q.pop();
int u = t.c; int p = t.d;
vis[u][p] = 0;
if(p == k) return;
for(int i = hd[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(dis[u][p] + edge[i].w < dis[v][p+1]){
dis[v][p+1] = dis[u][p] + edge[i].w;
if(!vis[v][p+1 ]){
vis[v][p+1] = 1;
q.push((Node){v, p+1});
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= m; i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
memset(dis, 0x3f, sizeof dis);
spfa();
int ans = 0x3f3f3f3f;
for(int i = 0; i <= k; i++){
ans = min(ans, dis[n][i]);
}
if(ans > 0x3f3f3f3f/2) cout<<"impossible"<<endl;
else cout<<ans<<endl;
return 0;
}
/*
1-2-3-4
\ |
5 |
\ /
6
入队： 1 5 2 6 3 （6出队的时候，将3更新，但3已经在队中，那么3到底是第3层还是第4层，3出队的时候如何更新4？）
*/
标签：cnt,853,int,短路,vis,edge,边数,include,dis From： https://www.cnblogs.com/caterpillor/p/17739325.html