霉利的题解（1）

dwandjk · 2024-12-29 11:20:42 · 题解

首先，看到这个题是单源最短路，那就应该想到dij或spfa。 写完后要注意可能会有重边，而且如果无法到达要输出“No answer”。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e3+10;
ll n,m,x,y,l,a[N][N],dis[N],f[N],path[N],sum=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>l;
        if(a[x][y]==0 || a[x][y]>l){//判断是否有重边
            a[x][y]=l;
        }
    }
    for(int i=1;i<=n;i++){
        dis[i]=2e9+10;//初始化
    }
  //dij模版
    dis[1]=0;//原点到原点距离为1
    path[1]=1;//原点到原点有一条路径
    for(int i=1;i<=n;i++){
        ll p=-1;
        for(int j=1;j<=n;j++){
            if(!f[j] && (p==-1 || dis[j]<dis[p])){
                p=j;
            }
        }
        f[p]=1;
        for(int j=1;j<=n;j++){
            if(!f[j] && a[p][j] && dis[p]+a[p][j]<dis[j]){//最短路径变小，路径数量归零后加上上一个点的数量
                dis[j]=dis[p]+a[p][j];
                path[j]=path[p];
            }else if(!f[j] && a[p][j] && dis[p]+a[p][j]==dis[j]){//如果最短路径相等，路径数量相加
                path[j]+=path[p];
            }
        }
    }
    if(dis[n]==2e9+10){//判断是否能到达
        cout<<"No answer";
    }else{
        cout<<dis[n]<<" "<<path[n];
    }
}