|
ude
#include
#include
#include
#include
using namespace std; typedef long long ll; const int maxn=1000000+5; const int max_dis=1e9 + 5; struct Edge{int to,dis,next;}graph[maxn]; struct edge{int from,to,dis;}g[maxn]; int T; int n,Q; int num; int d[maxn]; bool vis[maxn]; int head[maxn]; typedef pair
P; void Clear(){ num=0; memset(head,-1,sizeof(head)); memset(graph,0,sizeof(graph)); } void add(int u,int v,int dis){ graph[num].to=v; graph[num].dis=dis; graph[num].next=head[u]; head[u]=num++; } void input(){ scanf(%d%d,&n,&Q); Clear(); for(int i=0;i
,greater
>q; while(q.size()) q.pop(); d[1]=0; q.push(P(0,1)); while(q.size()){ P p=q.top(); q.pop(); int v=p.second; if(d[v]
-1;k=graph[k].next){ if(d[graph[k].to]>d[v]+graph[k].dis){ d[graph[k].to]=d[v]+graph[k].dis; q.push(P(d[graph[k].to],graph[k].to)); } } } ll ret=0; for(int i=1;i<=n;i++) ret+=d[i]; return ret; } ll spfa(){ memset(vis,false,sizeof(vis)); fill(d+1,d+1+n,max_dis); queue
q; while(!q.empty()) q.pop(); d[1]=0; vis[1]=true; q.push(1); while(!q.empty()){ int v=q.front(); q.pop(); vis[v]=0; for(int k=head[v];k>-1;k=graph[k].next){ if(d[graph[k].to]>d[v]+graph[k].dis){ d[graph[k].to]=d[v]+graph[k].dis; if(!vis[graph[k].to]){ vis[graph[k].to]=true; q.push(graph[k].to); } } } } ll ret=0; for(int i=1;i<=n;i++) ret+=d[i]; return ret; } void dijkstra_solve(){ ll ans=dijkstra(); Clear(); for(int i=0;i
?
|