1. 题目

传送门＝￣ω￣＝

2. 题解

依然是最短路条数统计问题。
可以参见这两篇题解：
https://www.mina.moe/?p=1232
https://www.mina.moe/?p=1227

只不过这题有坑：
数据中存在重边，需要自行过滤掉。而且重边的权值可能不同，需要保存最小权值。

考虑到数据范围比较小，在 1000 级别，所以开个二位数组存两点间距离。

而且此题不同于上面两题，是有向图（上面两题都是无向图）。所以建立反向图，权值不变，交换边的起点终点，便于记忆化搜索。

代码：

#include <bits/stdc++.h>
using namespace std;
static const int ns=2005,ms=4000005;
int n,m,d[ns],ans[ns];
bool book[ns];
queue<int> que;
struct graph
{
    int head[ns],to[ms],nxt[ms],dis[ns][ns],gs;
    graph()
    {
        gs=0,memset(head,-1,sizeof(head));
        for(int i=0;i<ns;i++)for(int j=0;j<ns;j++)dis[i][j]=INT_MAX;
    }
    void push(int u,int v,int w)
    {
        if(dis[u][v]==INT_MAX)to[gs]=v,dis[u][v]=w,nxt[gs]=head[u],head[u]=gs++;
        else dis[u][v]=min(dis[u][v],w);
    }
}g,ug;
int dfs(int u)
{
    if(ans[u])return ans[u];
    for(int i=ug.head[u];i!=-1;i=ug.nxt[i])
        if(d[u]-ug.dis[u][ug.to[i]]==d[ug.to[i]])ans[u]+=dfs(ug.to[i]);
    return ans[u];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++)
        scanf("%d%d%d",&u,&v,&w),g.push(u,v,w),ug.push(v,u,w);
    for(int i=1;i<=n;i++)d[i]=INT_MAX;
    d[1]=0,que.push(1),book[1]=1;
    while(!que.empty())
    {
        int f=que.front();que.pop(),book[f]=0;
        for(int i=g.head[f];i!=-1;i=g.nxt[i])
            if(d[g.to[i]]>d[f]+g.dis[f][g.to[i]])
            {
                d[g.to[i]]=d[f]+g.dis[f][g.to[i]];
                if(!book[g.to[i]])que.push(g.to[i]),book[g.to[i]]=1;
            }
    }
    if(d[n]==INT_MAX){printf("No answer\n");return 0;}
    ans[1]=1,printf("%d %d\n",d[n],dfs(n));
    return 0;
}