记录编号	204443	评测结果	EEEEEEEEEE
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	0
用户昵称	FETS 1/3	是否通过	未通过
代码语言	C++	运行时间	0.738 s
提交时间	2015-11-04 12:26:40	内存使用	0.78 MiB

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=250;
const int maxm=30055;
int n,m,c;
struct edge
{
	int x;
	int y;
	int v;
	int next;
};
edge e[maxm];
int qdb[maxn];
int t=0;
inline void insert(int u,int v,int va)
{
	e[++t].x=u;
	e[t].y=v;
	e[t].v=va;
	e[t].next=qdb[u];
	qdb[u]=t;
}
/*int map[maxn][maxn];
int f[maxn][maxn];*/
int q[maxn*2];
int head=1;
int tail=0;
int ans=0;
int vis[maxn];
void bfs(int st)
{
	q[++tail]=st;
	vis[st]=1;
	ans+=c;
	for(;head<=tail;)
	{
		for(int i=qdb[st];i;i=e[i].next)
		{
			if(e[i].v<c)
			{
				ans+=c;
				vis[e[i].y]=1;
			}
			else
			{
				if(!vis[e[i].y])
				{	
					vis[e[i].y]=1;
					q[++tail]=e[i].y;
					ans+=e[i].v;
				}
				if(e[i].y==q[head])
				{
					ans-=c;
					ans+=e[i].v;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]);
			bfs(i);
	}
}
int main()
{
	/*memset(map,10,sizeof(map));
	scanf("%d %d %d",&n,&m,&c);
	int te=c*n;
	for(int i=1;i<=m;i++)
	{
		int x,y,v;
		scanf("%d %d %d",&x,&y,&v);
		f[x][y]=min(f[x][y],v);
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	memset(map,10,sizeof(map));
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				int tt=min(f[i][j]+c,f[i][k]+f[k][j]+2c);
				map[i][j]=in(f[i][j]+c,f[i][k]+f[k][j]+);
			}
		}
	}*/
	scanf("%d %d %d",&n,&m,&c);
	int te=c*n;
	for(int i=i;i<=m;i++)
	{
		int x,y,v;
		scanf("%d %d %d",&x,&y,&v);
		insert(x,y,v);
	}
	bfs(1);
	if(ans>te)
	{
		cout<<te;
	}
	else
		cout<<ans;
	return 0;
}