7-35 城市间紧急救援 (25 分)c语言（测试点二未通过）

原题：https://pintia.cn/problem-sets/15/problems/862

思路：对迪杰斯特拉算法进行一些添加，不仅要计算最短路径，还要计算最短路径的的条数和可调动起来最多的救援队伍。最后把路径条数和队伍数量输出，把选择的那条完整路径输出。

调试过很多例子了，都没发现问题。。第二个测试点就是没过。实在是没辙了。

#include<stdio.h>
#define MAXSIZE 1010
#define inf 666666666
int N,M,S,D;
int G[MAXSIZE][MAXSIZE];
int vis[MAXSIZE];
int ss[MAXSIZE][2];//救援队数量 0表示自带的数量 1表示沿着最短路径到自己的总数量
int dist[MAXSIZE];//最短距离 
int path[MAXSIZE];//记录来时的路径
int cnt[MAXSIZE];//记录路的条数 
int findmin()//找出S相邻路径最短的边 
{
	int i,min=inf,minindex=-1;
	for(i=0;i<N;i++)
	{
		if(G[S][i]&&min>dist[i]&&!vis[i])
		{
			min=dist[i];
			minindex=i;
		}		
	}
	return minindex;
}
void dijkstra()
{
	int i,j;
	dist[S]=0;
	vis[S]=1;
	cnt[S]=1;
	path[S]=-1;
	for(i=0;i<N;i++)
	{ 
		if(G[S][i])
		{
			dist[i]=G[S][i];
			path[i]=S;
		}
	}
	while(1)
	{
	int v;	
	v=findmin();
	if(v==-1)break;
	else vis[v]=1;
	for(i=0;i<N;i++)
	{
		if(G[v][i]&&dist[i]>G[v][i]+dist[v]&&!vis[i])
		{
			dist[i]=G[v][i]+dist[v];//更新路径长度
			ss[i][1]=ss[i][0]+ss[v][1];		
			path[i]=v;
		    cnt[i]=cnt[v];			
		}
		else if(G[v][i]&&dist[i]==G[v][i]+dist[v]&&!vis[i])
		{	
			cnt[i]+=cnt[v];
			if(ss[i][0]+ss[v][1]>ss[i][1])
			{
				ss[i][1]=ss[i][0]+ss[v][1];//更新带的救援队数量
				path[i]=v;//更新来时的路				
			}					
		}
	}
	}
}
int main()
{
	int i,x,y,z;	
	scanf("%d%d%d%d",&N,&M,&S,&D);	
	for(i=0;i<N;i++)
	{
		scanf("%d",&ss[i][0]);
		cnt[i]=1; 
		ss[i][1]=ss[i][0];
		dist[i]=inf;
		path[i]=-1;
	}
	for(i=0;i<M;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		G[x][y]=G[y][x]=z;
	}
	dijkstra();
	printf("%d %d\n",cnt[D],ss[D][1]+ss[S][0]);	
	int t=D;
	int road[MAXSIZE];
	i=0;	
	while(t!=-1)//存储来时的路,直到它为根 
	{
		road[i++]=t;
		t=path[t];
	}
	i--;
	while(i>=0)
	{	
	    if(i==0)	
		printf("%d",road[i]);
		else
		printf("%d ",road[i]);
		i--;
	}
	return 0;
}

测试点	提示	结果	分数	耗时	内存
0	sample	答案正确	12	15 ms	308 KB
1	5条不同的最短路	答案错误	0	10 ms	304 KB
2	最小N和M	答案正确	2	10 ms	208 KB
3	最大N和M，随机数据构成完全图	答案正确	4	65 ms	2232 KB

为此我特意找了几个五条以上最短路的例子，也没发现问题啊。。

麻了麻了。 

7 11 0 5
10 20 20 20 20 20 30
0 1 30
0 2 40
0 3 30
0 4 20
0 5 60
0 6 10
1 5 30
2 5 20
5 3 30
5 4 40
1 6 20
6 80
0 6 1 5
--------------------------------
Process exited after 0.9187 seconds with return value 0
请按任意键继续. . .