测试点记录

堆优化Dijkstra写的，我不李姐为什么挂了。。。

求路过dalao帮助一下这个蒟蒻。

#include <bits/stdc++.h>
const int maxn = 2007, maxm = 4e6+7, INF = 1e9+7;
int n, m, a, b, c;
int head[maxn], cnt, flag[maxn*maxn];
long long num[maxn], sum[maxn];
bool vis[maxn];
struct edge{
    int to, w, nxt;
}e[maxm];
struct node{
    int sum, id;
    node(int asum = 0, int aid = 0){
        sum = asum, id = aid;
    }
    bool operator<(const node &x) const{
        return x.sum < sum;
    }
};
std::priority_queue <node> q;
void addedge(int u, int v, int w){
    int Hash = u * 1000 + v;
    if(flag[Hash] != 0){
        e[flag[Hash]].w = std::min(e[flag[Hash]].w, w);
        return;
    }
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
    flag[Hash] = cnt;
}
int main(){
    std::scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        std::scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
    }
    for(int i = 1; i <= n; i++) sum[i] = INF;
    sum[1] = 0;
    num[1] = 1;
    int u;
    q.push(node(0, 1));
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        u = tmp.id;
        vis[u] = true;
        for(int i = head[u]; i != 0; i = e[i].nxt){
            int v = e[i].to;
            if(!vis[v]){
                if(sum[v] > sum[u] + e[i].w){
                    sum[v] = sum[u] + e[i].w;
                    num[v] = num[u];
                    q.push(node(sum[v], v));
                }
                else if(sum[v] == sum[u] + e[i].w) num[v] += num[u];
            }
        }
    }
    if(sum[n] == INF) std::printf("No answer");
    else std::printf("%lld %lld", sum[n], num[n]);
    return 0;
}