MornHus @ 2023-01-07 22:37:34
样例过了,但是16pts。 用的dijkstra+堆优化 可能存图方法有点奇怪:
#include<bits/stdc++.h>
#define maxn 100001
#define maxm 200001
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,u,v,w;
struct node{
int to,val;
};
bool vis[maxn];
vector<node>gragh[maxn];
int dis[maxn];
struct point{
int id,distance;
bool operator < (const point &a)const{
return distance<a.distance;
}
};
priority_queue<point>q;
inline void dijkstra(){
for(int i=1;i<=n;i++){
if(i==s)continue;
dis[i]=inf;
}
q.push({s,0});
while(!q.empty()){
point curr=q.top();q.pop();
if(vis[curr.id])continue;
vis[curr.id]=1;
for(int i=0;i<gragh[curr.id].size();i++){
if(dis[gragh[curr.id][i].to]>dis[curr.id]+gragh[curr.id][i].val){
dis[gragh[curr.id][i].to]=dis[curr.id]+gragh[curr.id][i].val;
q.push({gragh[curr.id][i].to,dis[gragh[curr.id][i].to]});
}
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
gragh[u].push_back({v,w});
}
dijkstra();
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
by Usada_Pekora @ 2023-01-07 22:57:04
@MornHus 默认大根堆。
by MornHus @ 2023-01-07 23:02:19
@Zyingyzzz 该怎样改呢?
by MornHus @ 2023-01-07 23:02:58
@Zyingyzzz 我把重载运算符的小于改成大于会CE
by Usada_Pekora @ 2023-01-07 23:04:28
@MornHus 你不能改里面那个?
by Ruiqun2009 @ 2023-01-07 23:04:42
@MornHus 这样:
struct point{
int id,distance;
bool operator < (const point &a)const{
return distance>a.distance;
}
};
by HeCao2008 @ 2023-01-07 23:05:24
@MornHus 我建立小根堆的办法:
priority_queue<int , vector<int> , greater <int> > q;
by Ruiqun2009 @ 2023-01-07 23:06:02
@HeCao2008 但你这样没有适配 point
啊
by MornHus @ 2023-01-07 23:06:06
@Zyingyzzz 谢谢,已经AC!
by HeCao2008 @ 2023-01-07 23:09:44
@Ruiqun2009 从别的地方复制过来的(
by HeCao2008 @ 2023-01-07 23:10:26
@Ruiqun2009 哦不对我是小丑,这道题要重载运算符