围观

这进攻第一不就只能是公牛了吗

高中时期,杜兰特被誉为全美第二高中生，第一是KB3，后来他死了。大学时期，杜兰特被誉为NCAA第二好的球员，第一是奥登，后来他废了。再后来，杜兰特被誉为第二有潜力的超级新星，第一是罗斯，后来他残了。现在杜兰特被誉为联盟第二好的球员，第一是詹姆斯。。。。阿杜，我看好你！

试试账户

努力的样子最美。

存储层

哈哈哈哈哈

PaperBye一个可智能改重的免费论文查重网站。

28

27

26

牛

#include<algorithm>
#include<string.h>
#include<bits/stdc++.h>
#include<stack>
#include<stdio.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n,m;
int maze[10005][10005];
int d[10005];
int pre[10005];
int pre1[10005][10005];
int d1[10005][10005];
int vis[10005];
stack<int >s;
void dij(int x){
memset(d , INF,sizeof(d));
memset(vis, 0 ,sizeof(vis));
for(int i = 1; i <= n; i ++){
d[i] = maze[x][i];
if(d[i] < INF&& d[i] != 0) pre[i] = x;
else pre[i] = -1;
}
d[x] = 0;
vis[x] = 0;
for(int i = 0; i < n;i ++){
int maxn = INF, flag = -1;
for(int j = 1; j <= n; j ++){
if(d[j] < maxn&&!vis[j]){
flag = j;
maxn = d[j];
}
}
vis[flag] = 1;
for(int j = 1; j <= n; j++){
if(!vis[j]){
if(d[j] > d[flag] + maze[flag][j]){
pre[j] = flag;
d[j] = d[flag] + maze[flag][j];
}
}
}
}
}
int main()
{
printf("请输入城市的个数及路的个数:\n");
scanf("%d %d",&n,&m);
memset(maze, INF, sizeof(maze));
for(int i = 1; i <= n;i ++) maze[i][i] = 0;
printf("输入两个城市以及两城市之间的距离:\n");
for(int i = 0; i < m; i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
maze[x][y] = min(maze[x][y], z);
maze[y][x] = min(maze[y][x], z);
}
while(1){
int y;
printf("查询每个点之间的最短距离请输入1 单源最短路径请输入 2 退出输入 0\n");
scanf("%d",&y);
if(y == 0) break;
if(y == 1){
for(int i = 1; i <= n;i ++){
for(int j = 1; j <=n;j ++){
d1[i][j] = maze[i][j];
if(i != j&&d1[i][j] < INF){
pre1[i][j] = i;
}
else pre1[i][j] = -1;
}
}
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n;j ++){
if(d1[i][j] > d1[i][k] + d1[k][j]){
cout << 1 << endl;
d1[i][j] = d1[i][k] + d1[k][j];
pre1[i][j] = k;
}
}
}
}
while(1){
int flag;
printf("查询所有城市之间的距离请输入 1 某两个之间的距离请输入 2 退出请输入 0\n");
scanf("%d",&flag);
if(flag == 0) break;
if(flag == 1){
printf("各个城市之间的最短距离为:\n");
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j++){
printf("%d -> %d: %d\n", i , j, d1[i][j]);
}
}
}
else{
int a,b;
printf("输入两个城市:\n");
scanf("%d%d",&a,&b);
printf("点%d到点%d的最短路径为: ",a,b);
printf("%d ",a);
int c = a, d = b;
while(1){
if(a == pre1[a][b]) break;
printf("%d ", pre1[a][b]);
a = pre1[a][b];
}
printf("%d\n",d);
printf("最短距离为: %d\n",d1[a][b]);
}
}
}
if(y == 2){
printf("输入要查询的城市:\n");
int x;
scanf("%d",&x);
dij(x);
while(1){
printf("查询%d点到某个城市之间的最短路径请输入 1， 到所有点的最短距离请输入 2 退出为 0: \n",x);
int flag;
scanf("%d",&flag);
if(flag == 0) break;
if(flag == 1){
int a;
printf("输入要查询的点\n");
scanf("%d",&a);
s.push(a);
while(1){
if(pre[a] == x)break;
s.push(pre[a]);
a = pre[a];
}
s.push(x);
while(!s.empty()){
int b = s.top();
s.pop();
printf("%d ",b);
}
printf("\n");
}
if(flag == 2){
printf("%d点到其他城市的最短距离为:\n",x);
for(int i = 1; i <= n; i++){
printf("%d ",d[i]);
}
printf("\n");
}
}
}
}
}

帅