题目描述
求最短路和第二短路的方案和。
样例
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1
3
2
算法1
(Dijkstra)
显然跑最短路并且计数即可。
计数方法:
如果有条路到某一点时长度相等,那么这一点的到达方案数就为这几条路起点方案的和。
所以此题基本是模板。
C++ 代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
int to,v,next;
}s[10100];
int ls=1,head[1010];
void link(int a,int b,int c){
s[ls].to=b;
s[ls].v=c;
s[ls].next=head[a];
head[a]=ls++;
}
int dis[2][1010];
int sum[2][1010];
struct point{
int u,v;
};
bool operator < (const point a,const point b){
return a.v>b.v;
}
priority_queue<point>sq;
int n;
int dij(int st,int t){
for(int i=0;i<=n;i++) dis[0][i]=dis[1][i]=sum[0][i]=sum[1][i]=2000000000;
dis[0][st]=0;sum[0][st]=1;
sq.push((point){st,0});
point tmp;
while(!sq.empty()){
tmp=sq.top();sq.pop();
int k=-1,v,y;
if(dis[0][tmp.u]==tmp.v) k=0;
if(dis[1][tmp.u]==tmp.v) k=1;
if(k==-1) continue;
//printf("**%d %d %d\n",tmp.u,tmp.v,k);
for(int i=head[tmp.u];i;i=s[i].next){
v=tmp.v+s[i].v;y=s[i].to;
//printf("***%d %d\n",y,v);
if(dis[0][y]>v){//大于就把原来的往后推
dis[1][y]=dis[0][y];
sum[1][y]=sum[0][y];
dis[0][y]=v;
sum[0][y]=sum[k][tmp.u];
sq.push((point){y,v});
}
else
if(dis[0][y]==v){//等于就加上计数
sum[0][y]+=sum[k][tmp.u];
}
else
if(dis[1][y]>v){//维护次小
dis[1][y]=v;
sum[1][y]=sum[k][tmp.u];
sq.push((point){y,v});
}
else
if(dis[1][y]==v){
sum[1][y]+=sum[k][tmp.u];
}
}
}
if(dis[0][t]==dis[1][t]-1){/*printf("qqc\n");*/return sum[0][t]+sum[1][t];}//最短和次短相差1再相加
return sum[0][t];
}
int main(){
int T;
cin>>T;
while(T--){
int m,a,b,c;
for(int i=0;i<=n;i++) head[i]=0;
ls=1;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
link(a,b,c);
}
int st,t;
scanf("%d%d",&st,&t);
printf("%d\n",dij(st,t));
}
return 0;
}
请问
dis[1][y]
和dis[0][y]
sum[1][y] sum[0][y] 分别代表什么?可以讲讲吗,博主dis是记录长度,sum记录个数;同时,0代表的是最短路,1代表的是严格次短路