```cpp
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct dot
{
long long bianh,road;
bool operator <(dot tmp)const{
return tmp.road<road;
}
};
long long n[2001][2001];
long long dijk[100010];
int have[100010];
int count[100010];
const long long inf=1e10;
int main()
{
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=2000;j++)n[i][j]=inf;
}
int b,m;
cin>>b>>m;
priority_queue<dot>q;
for(int i=1;i<=m;i++)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
n[t1][t2]=t3;
}
for(int i=1;i<=b;i++)
{
dijk[i]=inf;
}
int x1,x2;
x1=1,x2=b;
count[x1]=1;
dijk[x1]=0;
q.push({x1,0});
for(int i=1;i<=b;i++) have[i]=1;
for(int i=1;i<=b;i++)
{
int now=-1;
while(now==-1){
if(q.empty())break;
int t1=q.top().bianh;
q.pop();
if(have[t1])now=t1;
}
if(now==-1)break;
have[now]=0;
for(int tmp=1;tmp<=b;tmp++)
{
if(!have[tmp])continue;
if(dijk[now]+n[now][tmp]<dijk[tmp])
{
dijk[tmp]=dijk[now]+n[now][tmp];
q.push({tmp,dijk[tmp]});
count[tmp]=count[now];
//cout<<now<<' '<<tmp2<<' '<<count[tmp2]<<'\n';
}
else if(dijk[now]+n[now][tmp]==dijk[tmp])
{
count[tmp]+=count[now];
//cout<<now<<' '<<n[tmp][1]<<' '<<count[n[tmp][1]]<<" 1\n";
}
}
}
for(int i=1;i<=b;i++)
{
//cout<<count[i]<<' ';
}
if(dijk[x2]==inf)
{
cout<<"No answer";
}
else
{
cout<<dijk[x2]<<' '<<count[x2];
}
return 0;
}
```
by anke2017 @ 2024-02-28 13:52:43
~~其实有没有堆优化一样复杂度~~
by anke2017 @ 2024-02-28 13:56:55
此帖结，死因：没有把读入的边取最短
by anke2017 @ 2024-03-29 13:41:10