玄关求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
const double dinf=1.79e308;
const int x3f=0x3f3f3f3f;
const int maxn=3010;
int n,m,a,b,ans[maxn],g[maxn][maxn],dist[maxn];
bool vis[maxn];
void dij(){
	priority_queue<pii,vector<pii>,greater<pii>>q;
	memset(dist,0x3f,sizeof(dist));
	q.push({1,0});
	dist[1]=0;
	ans[1]=1;
	while(!q.empty()){
		pii p=q.top();
		q.pop();
		if(vis[p.x])continue;
		vis[p.x]=1;
		for(int i=1;i<=n;i++){
			if(dist[p.x]+g[p.x][i]<dist[i]){
				dist[i]=dist[p.x]+g[p.x][i];
				q.push({i,-dist[i]});
				ans[i]=ans[p.x];
			}
			else if(dist[p.x]+g[p.x][i]==dist[i]){
				ans[i]+=ans[p.x];
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=min(g[u][v],w);
	}
	dij();
	if(dist[n]>=x3f){
		cout<<"No answer";
	}
	else{
		cout<<dist[n]<<' '<<ans[n];
	}
}