Poj 3463 Sightseeing

题目传送门

本题题意为，给你一个点和边集合，要你建图之后找出最短路和次短路的条数和，并且只有当最短路和次短路相差1才会统计。学长讲解方法之后，几乎照模板写出~
弱渣一枚，请问我可以不学图论吗~~我选择死亡，代码如下

///最短路和次短路

#include<stdio.h>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
#define inf 0x3fffffff

struct node{
   int to,next;
   int len;
}Edge[10010];
int vis[1010][2],dis[1010][2];//dis[i][0]代表最短路，dis[i][1]代表次短路
int head[1010],cnt[1010][2];//dis[i][0]代表最短路条数，dis[i][1]代表次短路条数
int n,m,num;
void addedge(int st,int en,int len)
{
 Edge[num].to=en;
 Edge[num].len=len;
 Edge[num].next=head[st];
 head[st]=num++;
}

void dij(int st,int en)
{
 memset(vis,0,sizeof(vis));
 memset(cnt,0,sizeof(cnt));
 for(int i=1;i<=n;i++)
 {
 dis[i][0]=dis[i][1]=inf;
 }
 dis[st][0]=0;
 cnt[st][0]=1;
 int mark,minn,flag;
 for(int i=1;i<=2*n-1;i++)
 {
 minn=inf;//找新的最短路和新的次短路
 for(int j=1;j<=n;j++)
 {
 if(!vis[j][0]&&minn>dis[j][0])
 {
 mark=j;
 flag=0;
 minn=dis[j][0];
 }
 else if(!vis[j][1]&&minn>dis[j][1])
 {
 mark=j;
 flag=1;
 minn=dis[j][1];
 }
 }
 if(minn==inf)break;
 vis[mark][flag]=1;
 for(int j=head[mark];j!=-1;j=Edge[j].next)///更新和mark相连的边
 {
 int v=Edge[j].to;
 if(dis[v][0]>minn+Edge[j].len)
 {
 dis[v][1]=dis[v][0];
 cnt[v][1]=cnt[v][0];
 dis[v][0]=minn+Edge[j].len;
 cnt[v][0]=cnt[mark][flag];
 }
 else if(dis[v][0]==minn+Edge[j].len)///等于最短路，更新方法数
 {
 cnt[v][0]+=cnt[mark][flag];
 }
 else if(dis[v][1]>minn+Edge[j].len)
 {
 dis[v][1]=minn+Edge[j].len;
 cnt[v][1]=cnt[mark][flag];
 }
 else if(dis[v][1]==minn+Edge[j].len)
 {
 cnt[v][1]+=cnt[mark][flag];
 }
 }
 }
 if(dis[en][1]==dis[en][0]+1)
 cnt[en][0]+=cnt[en][1];
 printf("%d\n",cnt[en][0]);
}


int main()
{
 int tt,st,en;
 scanf("%d",&tt);
 while(tt--)
 {
 num=0;
 memset(head,-1,sizeof(head));
 scanf("%d%d",&n,&m);
 int u,v,w;
 while(m--)
 {
 scanf("%d%d%d",&u,&v,&w);
 addedge(u,v,w);
 }
 scanf("%d%d",&st,&en);
 dij(st,en);
 }
 return 0;
}