Aimee

很水的题目

只要把P1144改一下

需要注意的是这个题有重边，求方案数的话一定要去重！！

这就涉及到很有趣的问题。

要想成为顶尖高手
就要做到滴水不漏
--橙汁哥

从这个题我才知道我写的堆优化Dijkstra复杂度有问题

TLE起飞

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
struct qu{
    int v;
    int id;
    friend  bool operator < ( qu x,qu  y){
        return x.v>y.v;
    }
};
priority_queue <qu>q;
int p;
bool num[2001]; 
int head[2001];
struct e{
    int ne;
    int to;
    int v;
} ed[5000001];
int dis[2001];
int n,m;
int u,v,x;
int cnt[2001];
int idd[2001][2001];
qu tool,t;
void add(int f,int to,int v){
    p++;
    ed[p].ne=head[f];
    ed[p].v=v;
    ed[p].to=to;
    head[f]=p;
    return ;
}
void dij(){
    tool.id=1;
    tool.v=0;
    q.push(tool);
    while(!q.empty()){
        tool=q.top();
        q.pop();
        if(num[tool.id])
        continue;
        num[tool.id]=1;

        for(int i=head[tool.id];i;i=ed[i].ne){
            if(dis[ed[i].to]>dis[tool.id]+ed[i].v){
                dis[ed[i].to]=dis[tool.id]+ed[i].v;
                t.id=ed[i].to;
                t.v=dis[ed[i].to];
                q.push(t);
                cnt[ed[i].to]=cnt[tool.id];     
            }else{
                if(dis[ed[i].to]==dis[tool.id]+ed[i].v){
                    cnt[ed[i].to]+=cnt[tool.id];
                }
            }
        }
    }
    return ;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&u,&v,&x);
        if(idd[u][v]){
            ed[idd[u][v]].v=min(ed[idd[u][v]].v,x);
        }else{
            add(u,v,x);
            idd[u][v]=p;
        }
    }
    memset(dis,0x7f,sizeof(dis));
    int maxx=dis[1]; 
    dis[1]=0;
    cnt[1]=1;
    dij();
    if(dis[n]<maxx){
        cout<<dis[n]<<" "<<cnt[n];
    }else{
        cout<<"No answer";
    }
    return 0;
}