|
原题：https://pintia.cn/problem-sets/15/problems/862
思路：对迪杰斯特拉算法进行一些添加，不仅要计算最短路径，还要计算最短路径的的条数和可调动起来最多的救援队伍。最后把路径条数和队伍数量输出，把选择的那条完整路径输出。
调试过很多例子了，都没发现问题。。第二个测试点就是没过。实在是没辙了。
#include
#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;idist[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;iss[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 |