提交记录

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;

int n,m;
int cnt[2003];
int dis[2003];
int mp[2003][2003];
struct node{
	int to,nxt,w;
}edg[6000003];
int head[2003],el;
void add(int fr,int to,int c){
	edg[++el]={to,head[fr],c};
	head[fr]=el;
}

priority_queue<pii,vector<pii>,greater<pii>>q;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		dis[i]=INT_MAX;
		for(int j=1;j<=n;j++){
			mp[i][j]=INT_MAX;
		}
	}
	for(int i=1;i<=m;i++){
		int x,y,z; cin>>x>>y>>z;
		if(z<mp[x][y]){
			add(x,y,z);
			mp[x][y]=z;
		}
	}
	
	q.push({0,1});
	cnt[1]=1;dis[1]=0;
	while(!q.empty()){
		int fr=q.top().second;
		q.pop();
		for(int i=head[fr];i;i=edg[i].nxt){
			int to=edg[i].to,w=edg[i].w;
			if(dis[fr]+w<dis[to]){
				dis[to]=dis[fr]+w;
				cnt[to]=cnt[fr];
				q.push({dis[to],to});
			}
			else if(dis[fr]+w==dis[to])cnt[to]+=cnt[fr];
		}
	}
	if(cnt[n])cout<<dis[n]<<' '<<cnt[n];
	else cout<<"No answer";
	return 0;
}