代码拉取完成,页面将自动刷新
同步操作将从 charlieshu/Algorithms 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
struct edge{
int stop,len;
};
int main(){
int n,m,s,t,g,q;
cin>>n>>m>>s>>t>>g>>q;
s--;
t--;
int h[n],l[n];
for(int i=0;i<n;i++)
cin>>h[i]>>l[i];
vector<edge> e[n];
for(int i=0;i<m;i++){
int start,stop,len;
cin>>start>>stop>>len;
start--;
stop--;
e[start].push_back({stop,len});
e[stop].push_back({start,len});
}
queue<int> qq;
int dis[n];
bool inq[n];
memset(dis,-1,sizeof(dis));
memset(inq,false,sizeof(inq));
dis[s] = 0;
for(auto i:e[s]){
dis[i.stop] = i.len;
qq.push(i.stop);
inq[i.stop] = true;
}
// for(int i=0;i<n;i++)
// cout<<dis[i]<<" ";
// cout<<endl;
while(!qq.empty()){
int now;
now = qq.front();
while(!qq.empty() && now != t && h[now]+dis[now]*q > l[now]){
dis[now] = -1;
qq.pop();
now = qq.front();
}
if(qq.empty())
break;
qq.pop();
for(auto i:e[now]){
if(i.stop != t && (dis[now]+i.len)*q+h[i.stop] > l[i.stop])
continue;
if(dis[i.stop] == -1){
dis[i.stop] = dis[now]+i.len;
if(!inq[i.stop]){
qq.push(i.stop);
inq[i.stop] = true;
}
}
else if(dis[now]+i.len < dis[i.stop]){
dis[i.stop] = dis[now]+i.len;
if(!inq[i.stop]){
qq.push(i.stop);
inq[i.stop] = true;
}
}
}
// cout<<1<<endl;
}
if(dis[t] == -1)
cout<<"wtnap wa kotori no oyatsu desu!";
else
cout<<dis[t];
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。