HDU 3193

谁能提供 hack 数据啊。

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned ll
#define ldb long db
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=55;
int n,m,u,v,w,s,t,dis1[N],dis2[N],cnt1[N],cnt2[N];
vector<pii> e[N];
priority_queue<piii,vector<piii>,greater<piii> > que;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	while(cin>>n>>m>>s>>t){
		memset(dis1,0x3f,sizeof dis1);
		memset(dis2,0x3f,sizeof dis2);
		memset(cnt1,0,sizeof cnt1);
		memset(cnt2,0,sizeof cnt2);
		for(int i=0;i<n;++i) e[i].clear();
		while(m--){
			cin>>u>>v>>w;
			e[u].pb({v,w});
		}
		dis1[s]=0;
		cnt1[s]=1;
		que.push({0,{1,s}});
		while(!que.empty()){
			piii cur=que.top(); que.pop();
			if(cur.F>dis2[cur.S.S]) continue;
			for(pii i:e[cur.S.S]){
				int td=cur.F+i.S,tc;
				if(cur.S.F==1) tc=cnt1[cur.S.S];
				else tc=cnt2[cur.S.S];
				if(dis1[i.F]>td){
					swap(td,dis1[i.F]);
					swap(tc,cnt1[i.F]);
					que.push({dis1[i.F],{1,i.F}});
				}
				else if(dis1[i.F]==td) cnt1[i.F]+=tc;
				if(dis1[i.F]<td && dis2[i.F]>td){
					dis2[i.F]=td;
					cnt2[i.F]=tc;
					que.push({dis2[i.F],{2,i.F}});
				}
				else if(dis2[i.F]==td) cnt2[i.F]+=tc;
			}
		}
		cout<<dis2[t]<<' '<<cnt2[t]<<'\n';
	}
	return 0;
}
//Arcana.