题意：求最短路和比最短路长度多1的次短路的个数
本来想图(有)方(模)便(版)用spfa的，结果妹纸要我看看dijkstra怎么解....
写了三遍orz
Ver1.0：堆优化+邻接表，WA
//不能用堆优化+邻接表，因为需要处理dis[i][0]和dis[i][1]两套，如果都挤到一个堆里就乱套了 #include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int Ni = ;
const int INF = <<;
struct node
{ //eg[i].x eg[i].d i:start x:end d:distance
int x,d;
node(){}
node(int a,int b){x=a;d=b;}
bool operator < (const node & a) const //用于优先队列, 取距离原点最近的点
{
if(d==a.d) return x<a.x;
else return d > a.d;
}
};
vector<node> eg[Ni];
int dis[Ni][],cnt[Ni][],n,T; void Dijkstra(int s) //1.比最短路短2.等于最短路3.长于最短路但短于次短路4.等于次短路
{
memset(dis,,sizeof(dis));
memset(cnt,,sizeof(cnt)); int i;
for(i=;i<=n;i++)
{
dis[i][]=INF;
dis[i][]=INF;
}
dis[s][]=;
dis[s][]=;
priority_queue<node> q; //q：优先队列，用来取离原点最近的顶点
q.push(node(s,dis[s][])); //初始只有一个原点自己
while(!q.empty())
{
node x=q.top();q.pop();
for(i=;i<eg[x.x].size();i++)
{
node y=eg[x.x][i];
if(dis[y.x][]>x.d+y.d) //
{
cnt[y.x][]=;
cnt[y.x][]=;
dis[y.x][]=dis[y.x][];
dis[y.x][]=x.d+y.d;
q.push(node(y.x,dis[y.x][]));
}
else if (dis[y.x][]==x.d+y.d) //
{
cnt[y.x][]++;
}
else if ((dis[y.x][]<x.d+y.d)&&(x.d+y.d<dis[y.x][])) //
{
cnt[y.x][]=;
dis[y.x][]=x.d+y.d;
}
else if (x.d+y.d==dis[y.x][]) //
{
cnt[y.x][]++;
}
}
}
} void debug()
{
cout<<"Debug only"<<endl;
for (int i=;i<=n;i++)
printf("%d - %d %d - %d %d\n",i,dis[i][],cnt[i][],dis[i][],cnt[i][]);
cout<<ans1<<" "<<ans2<<endl; } int main()
{
scanf("%d",&T);
while (T--)
{
int a,b,d,m,k,st;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) eg[i].clear();
while(m--)
{
scanf("%d%d%d",&a,&b,&d);
eg[a].push_back(node(b,d));
}
scanf("%d %d",&k,&st);
Dijkstra(k); debug1(); int t1=dis[st][],t2=dis[st][],ans1=cnt[st][],ans2;
if (t2-t1==)
ans2=cnt[st][];
else ans2=;
printf("%d\n",ans1+ans2);
} return ;
}
Ver2.0：邻接矩阵，WA
//不能用邻接矩阵，因为会有重边 #include <iostream>
#include <cstring>
using namespace std;
#define MAXINT 9999999 int minx,minj,x,y,t,k,n,m,tmp,st,flag;
int v[][],d[][],cnt[][],a[][]; int main()
{
int T;
cin>>T;
while (T--)
{
cin>>n>>m;
memset(a,,sizeof(a));
memset(d,MAXINT,sizeof(d));
memset(v,,sizeof(v));
memset(cnt,,sizeof(cnt)); for (int i=;i<=m;i++)
{
cin>>x>>y>>t;
a[x][y]=t;
}
cin>>k>>st;
d[k][]=; //d[k][2]=0;
cnt[k][]=; // cnt[k][2]=1; for (int i=;i<=*n;i++)
{
minx=MAXINT;
for (int j=;j<=n;j++)
{
if ((v[j][]==)&&(d[j][]<minx))
{
minx=d[j][];
minj=j;
flag=;
}
if ((v[j][]==)&&(d[j][]<minx))
{
minx=d[j][];
minj=j;
flag=;
}
}
v[minj][flag]=;
for (int j=;j<=n;j++)
// if ((v[j][1]==0)&&(a[minj][j]>0))
if (a[minj][j]>)
{
tmp=minx+a[minj][j]; if (tmp<d[j][])
{
d[j][]=d[j][];
d[j][]=tmp;
cnt[j][]=cnt[j][];
cnt[j][]=cnt[minj][flag];
}
else if (tmp==d[j][])
{
cnt[j][]+=cnt[minj][flag];
}
else if (tmp<d[j][])
{
d[j][]=tmp;
cnt[j][]=cnt[minj][flag];
}
else if (tmp==d[j][])
{
cnt[j][]+=cnt[minj][flag];
}
}
} for (int i=;i<=n;i++)
cout<<d[i][]<<" "<<cnt[i][]<<" = "<<d[i][]<<" "<<cnt[i][]<<endl;
cout<<endl;
int t1=d[st][],t2=d[st][],ans1=cnt[st][],ans2;
if (t2==t1+) ans2=cnt[st][]; else ans2=;
cout<<ans1+ans2<<endl;
}
return ;
}
Ver3.0：朴素n^2算法+邻接表 AC
#include <stdio.h>
#include <string.h>
#define INF 999999 struct node
{
int to,dat;
}edge[][]; int cnt[][],d[][],vis[][];
int x,y,z,n,m,T,st,ed; void insert_node(int x,int y,int z)
{
edge[x][].dat++;
int tmp=edge[x][].dat;
edge[x][tmp].to=y;
edge[x][tmp].dat=z;
} void dijkstra()
{
memset(vis,,sizeof(vis));
memset(d,INF,sizeof(d));
memset(cnt,,sizeof(cnt));
d[st][]=;
cnt[st][]=; for (int i=;i<=*n;i++)
{
int minj,flag,minx=INF;
for (int j=;j<=n;j++)
if ((vis[j][]==)&&(d[j][]<minx))
{
minx=d[j][];
minj=j;
flag=;
}
else if ((vis[j][]==)&&(d[j][]<minx))
{
minx=d[j][];
minj=j;
flag=;
}
vis[minj][flag]=;
int tmp=edge[minj][].dat;
for (int j=;j<=tmp;j++)
{
int yy=edge[minj][j].to;
int zz=edge[minj][j].dat;
//if (vis[yy][flag]==0)
//{
int tm=minx+zz;
if (tm<d[yy][])
{
d[yy][]=d[yy][];
cnt[yy][]=cnt[yy][];
d[yy][]=tm;
cnt[yy][]=cnt[minj][flag];
}
else if (tm==d[yy][])
{
cnt[yy][]+=cnt[minj][flag];
}
else if (tm<d[yy][])
{
d[yy][]=tm;
cnt[yy][]=cnt[minj][flag];
}
else if (tm==d[yy][])
{
cnt[yy][]+=cnt[minj][flag];
}
//} } }
} int main()
{
// freopen("in.txt","r",stdin); scanf("%d",&T);
while (T--)
{
memset(edge,,sizeof(edge));
scanf("%d %d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
insert_node(x,y,z);
}
scanf("%d %d",&st,&ed); /*
for (int i=1;i<=n;i++)
for (int j=1;j<=edge[i][0].dat;j++)
printf("Debug: %d -> %d = %d\n",i,edge[i][j].to,edge[i][j].dat);
*/ dijkstra(); int tx,ty,ans2,ans1;
tx=d[ed][]; ty=d[ed][];
ans1=cnt[ed][];
if (ty-tx==) ans2=cnt[ed][];
else ans2=;
// printf("%Debug: %d %d %d %d\n",tx,ty,ans1,ans2);
printf("%d\n",ans1+ans2);
}
return ;
}
邻接表很少用到都不大会写了>_<
dij松弛的条件改变下，有四种情况
1.比最短路短2.等于最短路3.长与最短路但短于次短路4.等于次短路
d[i][0]记最短路， d[i][1]记次短路
注意这里：
int tm=minx+zz;
if (tm<d[yy][])
{
d[yy][]=d[yy][];
cnt[yy][]=cnt[yy][];
d[yy][]=tm;
cnt[yy][]=cnt[minj][flag];
}
else if (tm==d[yy][])
{
cnt[yy][]+=cnt[minj][flag]; //因为松弛操作是从minj点开始的
//（d[minj]+a[minj,j]<d[j]）
//所以记录cnt的时候要+=cnt[minj][flag]
//一开始以为直接+1就行，WA了
//前面的cnt[yy][0]=cnt[minj][flag]同理
}
else if (tm<d[yy][])
{
d[yy][]=tm;
cnt[yy][]=cnt[minj][flag];
}
else if (tm==d[yy][])
{
cnt[yy][]+=cnt[minj][flag];
}
Reference：
http://blog.csdn.net/wmn_wmn/article/details/7376707
http://www.cnblogs.com/Missa/archive/2012/08/31/2665244.html