RT

二维BFS T了 开O2 MLE了

源码如下 注释是调试

试过用short还是MLE

STL狗都不用

awa求大佬优化

顺便求正解时间复杂度多少awa

题解说不能DFS 只拿20

但我这可以拿40

//Dreams are the seedings of realities.
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int mod=10000;
int n,m,a1,a2,t0;
ll ans=0,res=0;

struct EDGE{
	int next,to,t;
}edge[50009];
int head[20009],tot=0;

void add_edge(const int &u,const int &v,const int &w){
	edge[++tot].t=w;
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0); 
	cin>>n>>m>>a1>>a2>>t0;
	for(int i=1;i<=n;++i)
		head[i]=-1;
	t0%=mod;
	for(int i=1,u,v,w;i<=m;++i){
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	queue<pair<int,int> > q;
	q.push(pair<int,int> (0,a1));
	int tn,now;
//	cout<<endl;
	while(!q.empty()){
		tn=q.front().first;
		now=q.front().second;
		q.pop();
		if(now==a2){
			++res;
			ans+=tn;
//			cout<<ans<<" "<<res<<endl;
			continue;
		}
		for(int i=head[now];i!=-1;i=edge[i].next){
			q.push(pair<int,int> (tn+edge[i].t,edge[i].to));
//			cout<<now<<" "<<edge[i].to<<" "<<tn+edge[i].t<<endl;
		}
	}
	--res;
	ans+=res*t0; 
	cout<<ans%mod<<endl;
	return 0;
}

祝各位大佬度过美好的每一天awa