\(dijkstra\)最短路径计数,注意判输入时的重复数据(=_=)
const int N=2010;
struct Node
{
int a,b,c;
bool operator<(const Node &W) const
{
if(a == W.a)
{
if(b == W.b)
return c<W.c;
else return b<W.b;
}
else return a<W.a;
}
};
set<Node> S;
vector<PII> g[N];
int dist[N];
bool vis[N];
int f[N];
int n,m;
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII>,greater<PII> > heap;
dist[1]=0;
heap.push({0,1});
f[1]=1;
while(heap.size())
{
int t=heap.top().se;
heap.pop();
if(vis[t]) continue;
vis[t]=true;
for(int i=0;i<g[t].size();i++)
{
int j=g[t][i].fi,w=g[t][i].se;
if(dist[j] > dist[t]+w)
{
dist[j]=dist[t]+w;
f[j]=f[t];
heap.push({dist[j],j});
}
else if(dist[j] == dist[t]+w)
{
f[j]+=f[t];
}
}
}
}
int main()
{
ios;
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
if(S.count({a,b,c})) continue;
S.insert({a,b,c});
g[a].pb({b,c});
}
dijkstra();
if(dist[n] == INF) cout<<"No answer"<<endl;
else cout<<dist[n]<<' '<<f[n]<<endl;
//system("pause");
}