霉利的题解（1）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e3+10;
ll n,m,x,y,l,a[N][N],dis[N],f[N],path[N],sum=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>l;
		if(a[x][y]==0 || a[x][y]>l){//判断是否有重边
			a[x][y]=l;
		}
	}
	for(int i=1;i<=n;i++){
		dis[i]=2e9+10;//初始化
	}
  //dij模版
	dis[1]=0;//原点到原点距离为1
	path[1]=1;//原点到原点有一条路径
	for(int i=1;i<=n;i++){
		ll p=-1;
		for(int j=1;j<=n;j++){
			if(!f[j] && (p==-1 || dis[j]<dis[p])){
				p=j;
			}
		}
		f[p]=1;
		for(int j=1;j<=n;j++){
			if(!f[j] && a[p][j] && dis[p]+a[p][j]<dis[j]){//最短路径变小，路径数量归零后加上上一个点的数量
				dis[j]=dis[p]+a[p][j];
				path[j]=path[p];
			}else if(!f[j] && a[p][j] && dis[p]+a[p][j]==dis[j]){//如果最短路径相等，路径数量相加
				path[j]+=path[p];
			}
		}
	}
	if(dis[n]==2e9+10){//判断是否能到达
		cout<<"No answer";
	}else{
		cout<<dis[n]<<" "<<path[n];
	}
}