社区讨论
dij样例都不过求助
P1342[CERC1998] 请柬参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo8uzm9l
- 此快照首次捕获于
- 2023/10/28 01:00 2 年前
- 此快照最后确认于
- 2023/10/28 01:00 2 年前
CPP
#include <iostream>
#include <queue>
using namespace std;
template<typename T=int>
inline T read(){
T X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
if(flag) return X;
return ~(X-1);
}
template<typename T=int>
inline void write(T X){
if(X<0) putchar('-'),X=~(X-1);
T s[20],top=0;
while(X) s[++top]=X%10,X/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar('\n');
}
const int N=2e6+5,M=2e6+5,inf=0x3f3f3f3f;
struct edge{
int to,nxt,val;
}e[2][M];
int n,m,s,u,v,w;
int head[N],top;
int dist[N],vis[N];
long long ans;
priority_queue<pair<int,int>> q;
void add(int u,int v,int w,int id){
top++;
e[id][top].to=v;
e[id][top].val=w;
e[id][top].to=head[u];
head[u]=top;
}
void dijkstra(int id){
for(int i=1; i<=n; i++) dist[i]=inf,vis[i]=0;
dist[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u]; i; i=e[id][i].nxt){
v=e[id][i].to;
if(dist[v]>dist[u]+e[id][i].val){
dist[v]=dist[u]+e[id][i].val;
q.push(make_pair(-dist[v],v));
}
}
}
}
int main(){
n=read(),m=read(),s=1;
while(m--){
u=read(),v=read(),w=read();
add(u,v,w,0);
add(v,u,w,1);
}
dijkstra(0);
for(int i=1; i<=n; i++) ans+=dist[i];
dijkstra(1);
for(int i=1; i<=n; i++) ans+=dist[i];
write(ans);
return 0;
}
rt,样例输出
回复
共 4 条回复,欢迎继续交流。
正在加载回复...