社区讨论
堆优化Dij写炸了,求助大佬
学术版参与者 5已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @lodoucal
- 此快照首次捕获于
- 2023/10/31 10:06 2 年前
- 此快照最后确认于
- 2023/11/07 00:43 2 年前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long int ll;
using namespace std;
struct node{
int diss,index;
bool operator <(const node b)const{
return this->diss > b.diss;
}
}tmp;
ll n,m,s[200010],t[200010],d[200010];
ll v[200010],dis[200010];
ll first[200010],next[400010],in_last[400010];
priority_queue <node> q;
int main(){
ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
cin>>n>>m;
for(int i = 1; i <= m; ++i){
cin>>s[i]>>t[i]>>d[i];
next[in_last[s[i]]] = i;
in_last[s[i]] = i;
if(!first[s[i]]) first[s[i]] = i;
}
memset(dis,127/3,sizeof(dis));
dis[1] = 0;
tmp.diss = 0, tmp.index = 1;
q.push(tmp);
while(q.size()){
tmp = q.top(),q.pop();
int ind = tmp.index;
if(v[ind]) continue;
v[ind] = 1;
for(int i = first[ind]; i ; i = next[i]){
int end = t[i],len = d[i];
if(dis[ind]+len < dis[t[i]]){
dis[t[i]] = dis[ind]+len;
tmp.diss = dis[t[i]];
tmp.index = end;
q.push(tmp);
}
}
}
cout<<dis[n]<<endl;
return 0;
}
就两个测试点,全WA了......
回复
共 15 条回复,欢迎继续交流。
正在加载回复...