lz在POJ(北大的OJ)上交了份代码,事先声明没有任何语法错误(请教练看过了),但是不知道为什么老是CE,可能是因为编译器版本太老了。求帮改出能编译过的代码。
就是很普通的最短路和次短路计数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
#define MAXN 1008
#define INF 30
#define Maxnum 1e8
#define M make_pair
typedef pair<int,int> pii;
void csh();
int n,m,s,f,vis[MAXN][8];
int dis[MAXN],dis2[MAXN]; // dis是s点到f点的最短路 , dis2是s点到f的次短路
int sum[MAXN],sum2[MAXN]; // sum是最短路路径计数 , sum2是次短路路径计数
vector<pii> a[MAXN*10];
void dijkstra(){
priority_queue< pair<int,pii> > q;
q.push({0,{s,1}});
dis[s]=sum[s]=1;
while(!q.empty()){
int d,x,t;
d=-q.top().first;
x=q.top().second.first,t=q.top().second.second;
int newsum=(t==1 ? sum[x] : sum2[x]);
q.pop();
if(vis[x][t]) continue;
vis[x][t]=1;
for(int i=0;i<a[x].size();i++){
int y=a[x][i].first;
int v=a[x][i].second;
int value=d+v;
if(value<dis[y]){
if(value<Maxnum){
dis2[y]=dis[y];
sum2[y]=sum[y];
q.push({-dis[y],{y,2}});
}
dis[y]=value;
sum[y]=newsum;
q.push({-dis[y],{y,1}});
}
else if(value==dis[y]){
sum[y]+=newsum;
}
else if(value<dis2[y]){
dis2[y]=value;
sum2[y]=newsum;
}
else if(value==dis2[y]){
sum2[y]+=newsum;
}
}
}
return ;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
csh();
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u].push_back(M(v,w));
}
scanf("%d%d",&s,&f);
dijkstra();
if(dis2[f]==dis[f]+1){
printf("%d\n",sum[f]+sum2[f]);
}else{
printf("%d\n",sum[f]);
}
}
return 0;
}
void csh(){
for(int i=0;i<n;i++) a[i].clear();
memset(dis,INF,sizeof(dis));
memset(dis2,INF,sizeof(dis2));
memset(sum,0,sizeof(sum));
memset(sum2,0,sizeof(sum2));
memset(vis,0,sizeof(vis));
return ;
}
跪谢