题意描述：

“RP餐厅”的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让HZH,TZY去送快餐了.

他们将自己居住的城市画了一张地图，已知在他们的地图上，有个地方。

而且他们目前处在标注为的小镇上，而送餐的地点在标注为的小镇。（有点废话）

除此之外还知道这些道路都是单向的，从小镇I到J需要花费的时间。

为了更高效快捷的将快餐送到顾客手中，他们想走一条从小镇到小镇花费最少的一条路。

但是他们临出发前，撞到因为在路上堵车而生气的FYY，深受启发，不能仅知道一条路线，万一。。。

于是，他们邀请FYY一起来研究起了下一个问题：这个最少花费的路径有多少条？

输入格式：

输入文件第一行为两个空格隔开的数，表示这张地图里有多少个小镇及有多少边的信息。

下面行，每行三个数，表示从小镇到小镇有道路相连且花费为.

输出格式：

输出文件包含两个数，分别是最少花费和花费最少的路径的总数.

两个不同的最短路方案要求：路径长度相同（均为最短路长度）且至少有一条边不重合。

若城市无法到达则只输出一个No answer;

Input & Output 's examples

Input 's eg

5 4
1 5 4
1 2 2
2 5 2
4 1 1

Output 's eg

4 2

数据范围和约定

对于的数据 ;

对于的数据 ,, .

不保证没有重边，自环。

分析

一句话题意：给你一张有向图，让你求出从到的最短路长度与最短路数量。

我们只需要一个最短路模板和一个计数操作即可。

Dijkstra的计数操作代码如下：

int ans[N];     //ans为最短路数量

if(dis[to] > dis[v] + edge[i].dis){     //如果需要进行松弛操作
    dis[to] = dis[v] + edge[i].dis;
    ans[to] = ans[v];   //就用新的最短路数量覆盖原来的最短路数量
    Q.push(make_pair(dis[to] , to));
}
else if(dis[to] = dis[v] + edge[i].dis){    //如果这是另一条最短路
    ans[to] += ans[v];  //将数量相加
}

计数之前不要忘记把ans[1]初始化为1

对于重边的话，我们很容易注意到的数据范围只有。

因此，我们直接开一个二维数组记录重边中最短的一条即可。

剩下的就是最短路模板了

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define N 500001
#define end head

using namespace std;

int n , m , s;

struct Edge{
    int to;
    ll dis;
    int last;
}edge[N];

int end[N];
int edge_num;

void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = Edge{to , dis , end[from]};
    end[from] = edge_num;
}

ll dis[N];
bool vis[N];
ll ans[N];

void Dijkstra(int s){
    #define pairs pair<ll  , ll >

    priority_queue<pairs , vector<pairs > , greater<pairs > > Q;
    for(int i = 1; i <= n; i ++){
        dis[i] = 0x3f3f3f3f;
    }
    dis[s] = 0;
    for(int i = 1; i <= n; i ++){
        Q.push(make_pair(dis[i] , i));
    }
    while(!Q.empty()){
        int now = Q.top().second;
        Q.pop();
        if(vis[now]){
            continue;
        }
        vis[now] = true;
        for(int i = end[now] ; i ; i = edge[i].last){
            int to = edge[i].to;
            if(dis[to] > dis[now] + edge[i].dis){   //最短路计数部分
                dis[to] = dis[now] + edge[i].dis;
                ans[to] = ans[now];
                Q.push(make_pair(dis[to] , to)); 
            }
            else if(dis[to] == dis[now] + edge[i].dis){
                ans[to] += ans[now];
            }
        }
    }
}

int map[2001][2001];

int main(){
    int l  , r;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> l >> r >> s;
        if(map[l][r] == false || map[l][r] > s){
            add_edge(l , r , s);
            map[l][r] = s;
        }
    }
    ans[1] = 1;
    Dijkstra(1);
    if(dis[n] == 0x3f3f3f3f){
        puts("No answer");
    }
    else{
        cout << dis[n] << " " << ans[n];
    }
    return 0;
}

THE END