注册登录

P1608 路径统计

最短路计数

这题要用dij，，不知道spfa为什么会出锅，也不会改

就对每个点记录一个cnt

每次更新最短路的时候就将x的cnt传给to

如果最短路相等，就给to的cnt加上x的cnt

然后就是dij板子，，其实就是个板子加上一点修改，，


#include<cstdio>
#include<queue>
using namespace std;
const int N=2005;
int head[N],d[N],ans[N];
int mp[N][N];
bool in[N];
int cnt,n,m;
struct node{
    int to,nxt,dis;
}e[(N*N)<<1];
struct edge{
    int val,num;
    bool operator < (const edge &x)const{
        return val>x.val;
    }
};
inline void add(int from,int to,int dis){
    e[++cnt]=(node){to,head[from],dis};
    head[from]=cnt;
}

priority_queue<edge>q;
void spfa(){
    q.push((edge){0,1});
    d[1]=0;ans[1]=1;
    while(!q.empty()){
        int t=q.top().num;
        q.pop();
        if(in[t])continue;
        in[t]=1;
        for(int i=head[t];i!=0;i=e[i].nxt){
            if(!in[e[i].to]&&d[e[i].to]>d[t]+e[i].dis){
                d[e[i].to]=d[t]+e[i].dis;
                ans[e[i].to]=ans[t];
                q.push((edge){d[e[i].to],e[i].to});
            }
            else if(d[e[i].to]==d[t]+e[i].dis)
                ans[e[i].to]+=ans[t];
        }
    }
}
int main(){
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        if(mp[x][y]==0||mp[x][y]>z){
            add(x,y,z);mp[x][y]=z;
        }
    }
    for(int i=1;i<=n;++i)
        d[i]=1e9;
    spfa();
    if(d[n]==1e9)printf("No answer");
    else printf("%d %d",d[n],ans[n]);
    return 0;
}
知识兔
计算机