Submission #352453

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define rep2(x,from,to) for(long long x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 10000000000000000
typedef pair<long long ,long long> P;
struct edge
{
	long long to;
	long long cost;
};
edge ee;
long long D[400][400]; 
vector<edge> G[401];
long long d[401];
long long n,m;
long long a,b,c,k;
long long ans;
long long V,E;
void dijkstra(long long s)
{
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
	fill(d,d+V,INF);
	d[s]=0;
	while(!que.empty())
	{
		P p=que.top();que.pop();
		long long v=p.second;
		if(d[v]<p.first)continue;
		rep(i,G[v].size())
		{
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost)
			{
				d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	V=n;
	E=m;
	rep(i,m)
	{
		cin>>a>>b>>c;
		a--;b--;
		ee.to=a;
		ee.cost=c;
		G[b].push_back(ee);
		ee.to=b;
		G[a].push_back(ee);
	}
	rep(i,n)
	{
		dijkstra(i);
		rep(j,n)
		{
			D[i][j]=d[j];
		}
	}
	cin>>k;
	rep(t,k)
	{
		cin>>a>>b>>c;
		a--;b--;
		rep(i,n)
		{
			rep(j,n)
			{
				if(i==j)continue;
				if(D[i][a]+c+D[b][j]<D[i][j])
				{
					D[i][j]=D[i][a]+c+D[b][j];
				}
				if(D[i][b]+c+D[a][j]<D[i][j])
				{
					D[i][j]=D[i][b]+c+D[a][j];
				}
			}
		}
		ans=0;
		rep(i,n)rep2(j,i+1,n)
		{
			ans+=D[i][j];
		}
		cout<<ans<<endl;
	}
	return 0;
}

Submission Info

Judge Result