P1608

85分，代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int c[2010][2010];
vector< pair<int,int> >a[2010];
int d[2010],sum[2010];
bool f[2010];
void dj(){
	priority_queue< pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> >q;
	memset(d,0x3f3f3f3f,sizeof(d));
	q.push({1,0});
	d[1]=0;
	sum[1]=1;
	while(!q.empty()){
		pair<int,int> t=q.top();
		q.pop();
		int u=t.first;
		if(f[u]==false){
			f[u]=true;
			for(int i=1;i<=n;i++){
				int v=i;
				int w=c[u][i];
				if(w+d[u]<d[v]){
					d[v]=w+d[u];
					sum[v]=sum[u];
					q.push({v,d[v]});
				}
				else if(w+d[u]==d[v]){
					sum[v]+=sum[u];
				}
			}
		}
	}
	if(d[n]>=0x3f3f3f3f/2){
		cout<<"No answer";
	}
	else{
		cout<<d[n]<<" "<<sum[n]<<endl;
	}
}
int main(){
	cin>>n>>m;
	memset(c,0x3f,sizeof c);
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		c[x][y]=min(c[x][y],z);	
	}
	dj();
	return 0;
}