#include <bits/stdc++.h>
using namespace std;
struct node{
int v,w;
bool operator<(const node & x)const{
return w>x.w;
}
};
const int N=1010;
const int M=500010;
int n,m;
int hd[N],ver[M],nxt[M],w[M],tot=0;
void add(int x,int y,int z){
ver[++tot]=y;
w[tot]=z;
nxt[tot]=hd[x];
hd[x]=tot;
}
priority_queue<node>q;
int vis[N];
int bfs(int s,int t,int k){
node u,v;
u.v=s;u.w=0;
q.push(u);
while(q.size()){
u=q.top();
q.pop();
vis[u.v]++;
if(vis[u.v]==k&&u.v==t)return u.w;
if(vis[u.v]>k)continue;
for(int i=hd[u.v];i;i=nxt[i]){
v.v=ver[i];
v.w=u.w+w[i];
q.push(v);
}
}
return -1;
}
int main(){
int s,t,k;
cin>>n>>m;
int x,y,z;
for(int i=0;i<m;i++){
cin>>x>>y>>z;
add(x,y,z);
}
cin>>s>>t>>k;
if(s==t&&m==0)cout<<-1;
else cout<<bfs(s,t,k);
return 0;
}
我去你个大西瓜
作者：
KingArthur
,
2021-05-05 18:51:23
,
所有人可见
,
阅读 551
KingArthur
,
2021-05-05 18:51:23
,
所有人可见
,
阅读 551
while(q.size()){
u=q.top();
q.pop();
vis[u.v];
if(vis[u.v]==k&&u.v==t)return u.w;
if(vis[u.v]>k)continue;
for(int i=hd[u.v];i;i=nxt[i]){
v.v=ver[i];
v.w=u.w+w[i];
q.push(v);
}
}
return -1;
}while(q.size()){
u=q.top();
q.pop();
vis[u.v];
if(vis[u.v]==k&&u.v==t)return u.w;
if(vis[u.v]>k)continue;
for(int i=hd[u.v];i;i=nxt[i]){
v.v=ver[i];
v.w=u.w+w[i];
q.push(v);
}
}
return -1;
}while(q.size()){
u=q.top();
q.pop();
vis[u.v];
if(vis[u.v]==k&&u.v==t)return u.w;
if(vis[u.v]>k)continue;
for(int i=hd[u.v];i;i=nxt[i]){
v.v=ver[i];
v.w=u.w+w[i];
q.push(v);
}
}
return -1;
}while(q.size()){
u=q.top();
q.pop();
vis[u.v];
if(vis[u.v]==k&&u.v==t)return u.w;
if(vis[u.v]>k)continue;
for(int i=hd[u.v];i;i=nxt[i]){
v.v=ver[i];
v.w=u.w+w[i];
q.push(v);
}
}
return -1;
}
？？？这和西瓜有什么关系?_?