LYqwq @ 2022-05-21 09:41:17
#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,样例输出
by barbatoss @ 2022-05-21 09:45:32
诶,让我看看
by barbatoss @ 2022-05-21 09:54:38
样例改过了,你看一下对不对,错的地方后面都加了注释,为了防止别人贺题,放云剪贴板了
by LYqwq @ 2022-05-21 10:00:42
谢谢xyj
by Chthologist7507 @ 2022-05-21 10:05:47
stoxyjorz