- BC20270041's blog
第十六讲笔记：Floyd算法
-
BC20270041
LV 1
@
2025-2-27 20:03:38
Floyd算法的特点
唯一一个多源的图论最短路算法，但是复杂度
判断每一个点k，然后再找i,j
满足以上三个条件久会更新
void Floyd(){
for(int k=0;k<n;k++){//每个要考虑的点
for(int i=0;i<n;i++){//起点
for(int j=0;j<n;j++){//终点
if(dot[i][k]!=INT_MAX&&dot[k][j]!=INT_MAX&&dot[i][k]+dot[k][j]<dot[i][j]){
dot[i][j]=dot[i][k]+dot[k][j];
}
}
}
}
}
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dot[123][123];
void init(){
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dot[i][j]=INT_MAX;
return ;
}
void Floyd(){
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
if(dot[i][k]!=INT_MAX&&dot[k][j]!=INT_MAX&&dot[i][j]>dot[i][k]+dot[k][j]){
dot[i][j]=dot[i][k]+dot[k][j];
}
}
return ;
}
int main(){
cin>>n>>m;
int a,b,c,temp;
init();
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
temp=min(min(dot[a][b],dot[b][a]),c);
dot[a][b]=temp;
dot[b][a]=temp;
}
Floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)cout<<"0 ";
else cout<<dot[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
#include<bits/stdc++.h>
#include<windows.h>
#include<stdio.h>
#include<conio.h>
#include<time.h>
using namespace std;
//第一章：创建变量
int flag[20][3]={};//1：是否存活，2：是否上挂，3：是否出过中pig，4：连续哈哈的次数
int protect[5][3]={};//盾、钟
string gun[15][10]={
{"玉","防","闪","甩剑",},{"戳","双戳","三戳","四戳"},{"暴击","重击","痛击","马丁","百变马丁"},{"重拳","天地","无向","马丁","百变马丁"},{"小猪","中猪","大猪","无猪","聪明无猪"},{"小电","中电","大电","雷神"},{"斩","元气斩","猪油斩"},{"狒狒（4玉1.5防）","狒狒（2.5甩剑）","暗黑狒狒","banana","dark-banana"},{"黑洞","白洞","虫洞","a","a"},{"CSP-J","CSP-S","NOIP","NOI","IOI"}
};
int player[50][5]={};//玩家的每个攻击的数量
double basic[20][3]={};//yu,fang,shuai,shan
struct fire{
int f,hh,sh;//能否防，能否哈哈，能否闪
double hurt;//伤害
double yu,fang,shuai,dian;//价格
}tool[50];
//第二章：初始化数据
void SetPos(int x,int y){
COORD pos; pos.X=y*2-1,pos.Y=x+1;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),pos);
}
void Color(int a){
if(a==0) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
if(a==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN|FOREGROUND_BLUE);
if(a==2) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);
if(a==3) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_BLUE);
if(a==4) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);
if(a==5) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN);
if(a==6) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);
if(a==7) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN);
if(a==8) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
}
void init(){
flag[1][1]=1;
flag[1][2]=1;
flag[2][1]=0;
flag[2][2]=0;
flag[3][1]=0;
flag[3][2]=0;
flag[4][1]=0;
flag[4][2]=0;
protect[1][1]=0;
protect[1][2]=0;
protect[2][1]=0;
protect[2][2]=0;
for(int i=0;i<50;i++)for(int j=0;j<5;j++)player[i][j]=0;
tool[1]={1,0,1,0.5,0.5};//ber
tool[2]={0,0,1,0.5};//2ber
tool[3]={0,0,1,1};//3ber
tool[4]={0,0,1,2};//4ber
tool[6]={0,1,0,0.6,1,1};//baoji
tool[7]={0,1,0,1};//zhongji
tool[8]={0,0,0,2};//tongji
tool[9]={0,0,0,4};//mading1
tool[10]={0,0,0,8};//baibian-mading1
tool[11]={0,0,0,0.5,1.5};//zhongquan
tool[12]={0,0,0,1};//tiandi
tool[13]={0,0,0,2};//wuxiang
tool[14]={0,0,0,4};//mading
tool[15]={0,0,0,8};//baibian-mading
tool[16]={1,1,0,0.5,1};//pig
tool[17]={0,1,0,1};//midpig
tool[18]={0,0,0,2};//hugepig
tool[19]={0,0,0,4};//no_pig
tool[20]={0,0,0,8};//smart_no_pig
tool[21]={1,0,1,0.5,0,0,0,1.5};//dian
tool[22]={0,0,1,1};//mid_dian
tool[23]={0,0,0,2};//big_dian
tool[24]={0,0,0,4};//lightening
tool[26]={1,1,0,0.5,0.5,0.5};//zhan
tool[27]={0,1,0,0.5};//yuanqi
tool[28]={0,0,0,1};//zhuyou
tool[31]={0,0,0,3.5,4,1.5};//feifei1
tool[32]={0,0,0,3.5,0,0,2.5};//feifei2
tool[33]={0,0,0,7};//anheifeifei
tool[37]={0,1,0,1};//whitehole;
tool[38]={0,0,0,2};//chongdong
tool[41]={1,1,0,0.5};//J
tool[42]={0,1,0,1};//S
tool[43]={0,0,0,2};//NOIP
tool[44]={0,0,0,4};//NOI
tool[45]={0,0,0,8};//IOI
}
void Slowsay(string a){
int l=a.size();
for(int i=0;i<l;i++){
cout<<a[i];
Sleep(2);
}
printf("\n");
}
void fiveSeconds(){
int timeup=5;
Color(5);
while(timeup--){
cout<<timeup+1<<"秒后游戏继续"<<endl;
Sleep(1000);
}
Color(8);
return ;
}
//第三章：游戏第一层界面
void start_(){
SetPos(1,4),Color(2),cout<<"欢迎初一3班的热门游戏"<<endl;
SetPos(2,5),Color(6),cout<<"强力克制作弊大师"<<endl;
SetPos(3,6),Color(1),cout<<"制作:HF0310"<<endl;
SetPos(4,2),Color(5),cout<<"更新系列（当前版本：1.1）";
Color(8),cout<<"1键"<<endl;
SetPos(5,2),Color(4),cout<<"人机对打（未开发） ";
Color(8),cout<<"2键"<<endl;
SetPos(6,2),Color(3),cout<<"双人对战（不能联机） ";
Color(8),cout<<"3键"<<endl;
SetPos(7,2),Color(7),cout<<"退出游戏（本游戏没存档） ";
Color(8),cout<<"4键"<<endl;
}
void _story(){
char choose;
Color(7),Slowsay(" 作者介绍");
Color(2),Slowsay("初一三班：hfoj.net/blog/1918");
Color(6),Slowsay(" 禁止改编或者放入自己的博客");
Color(3),Slowsay(" 更新日志");
Color(1),Slowsay(" v1.0 2025年2月27日");
Color(8),Slowsay(" 创建此界面");
Color(1),Slowsay(" v1.1 2025年?月？日");
Color(8),Slowsay(" 完成基础玩法：双人对决");
Color(1),Slowsay(" 即将更新的模式");
Color(8),Slowsay(" 开局加入护盾、钟以及蕉");
Color(8),Slowsay(" 玩家（们）可以自己定义");
Color(5),Slowsay(" 按下a回到主界面");
while(choose!='a')choose=_getch();
system("cls");
return ;
}
void not_write(){
Color(1);
Slowsay("都说了没开发了你TM还点");
Color(8);
Sleep(3000);
}
//第四章到第十一章是双人玩法
//第四章：基础物资
string __basic(int x){
int choose;
Color(2);
Slowsay("基础物资系列如下");
Sleep(500);
for(int i=0;i<=3;i++){
Color(8);
cout<<gun[0][i]<<':';
Color(7);
cout<<basic[i][x]<<(i==3?" ":" ");
Color(1);
cout<<"按"<<i+1<<"键"<<endl;
Sleep(500);
}
Color(8);
cin>>choose;
if(choose!=1&&choose!=2&&choose!=3&&choose!=4){
Color(4);
Slowsay("无效输入，即将返回上一层");
Color(8);
Sleep(1500);
return "";
}
basic[choose-1][x]++;
cout<<"完成，你现在有";
cout<<basic[choose-1][x];
cout<<"个";
cout<<gun[0][choose-1];
Sleep(500);
return gun[0][choose-1];
}
//第五章：攻击方式
//九种攻击道具
void chuo(int flag){
not_write();
}
void baoji(int flag){
not_write();
}
void zhongqvan(int flag){
not_write();
}
void pig(int flag){
not_write();
}
void dian(int flag){
not_write();
}
void zhan(int flag){
not_write();
}
void feifei(int flag){
not_write();
}
void hole(int flag){
not_write();
}
void mobai(int flag){
not_write();
}
//攻击界面
string __fight(int x,int y){
//x表示玩家编号，y表示出的攻击方式
system("cls");
int answer;
cin>>answer;
bool flag=false;
Color(8);
Slowsay("你选择的系攻击手段如下：");
if(answer==1)chuo(flag);
if(answer==2)baoji(flag);
if(answer==3)zhongqvan(flag);
if(answer==4)pig(flag);
if(answer==5)dian(flag);
if(answer==6)zhan(flag);
if(answer==7)feifei(flag);
if(answer==8)hole(flag);
if(answer==9)mobai(flag);
return "";
}
//第六章：防具
string __protect(int x){
int f1=basic[1][x],f2=protect[1][x]/2;
int choose;
Color(2),cout<<"防具系列"<<endl;
Sleep(250);
Color(8),cout<<"你有"<<basic[1][x]<<"个防"<<endl;
Sleep(250);
Color(1),cout<<"你有"<<protect[1][x]<<"个盾"<<endl;
Sleep(250);
Color(7),cout<<"你有"<<protect[2][x]<<"个钟"<<endl;
Sleep(500);
if(f1)Color(1),cout<<"按1购买盾，当前够买"<<f1<<"个"<<endl;
else Color(4),cout<<"没有足够的防来买盾，1个防买1个盾"<<endl;
Sleep(250);
if(f2)Color(7),cout<<"按2购买钟，当前够买"<<f2<<"个"<<endl;
else Color(4),cout<<"没有足够的盾来买钟，2个盾买1个钟"<<endl;
Color(8);
cin>>choose;
if(choose==1&&f1){
basic[1][x]-=1;
protect[1][x]++;
Color(1),cout<<"完成，你现在有"<<protect[1][x]<<"个盾";
Sleep(500);
Color(8);
return "盾";
}else if(choose==2&&f2){
protect[2][x]++;
protect[1][x]-=2;
Color(1),cout<<"完成，你现在有"<<protect[2][x]<<"个钟";
Sleep(500);
Color(8);
return "钟";
}else{
Color(4);
Slowsay("输入失败，即将返回上一层");
Sleep(1500);
Color(8);
return "";
}
return "";
}
//第七章
string __prop(int x){
int choose;
Color(2),Slowsay("请输入特殊道具的编号");
Color(1),Slowsay("这些道具在关键时能发挥作用");
Color(3),cout<<"你现在";
Sleep(10);
if(flag[2][x]==0)cout<<"不";
Slowsay("处于上挂状态");
Color(7);
if(!flag[2][x])Slowsay("1：上挂（无敌开关）");
else Slowsay("2：下挂（再不跑可能就没了）");
Slowsay("3：举报（预判大师）\n4：哈哈（反弹部分猪、斩、膜拜以及暴击）");
Color(8);
cin>>choose;
if(choose!=flag[2][x]+1&&choose!=3&&choose!=4){
Color(4);
system("cls");
Slowsay("无效输入，即将返回上一层");
Color(8);
Sleep(1500);
return "";
}if(choose==3){
Color(1),Slowsay("举报成功，任何玩家上挂时死亡");
Color(8);
Sleep(500);
system("cls");
return "举报";
}else if(choose==4){
flag[4][x]++;
Color(1),Slowsay("完成，小心不要连续三次哈哈");
Color(8);
Sleep(500);
system("cls");
return "哈哈";
}else if(choose==1&&flag[2][x]==0){
flag[2][x]=1;
Color(6),Slowsay("上挂成功，记得下来");
Color(8);
Sleep(500);
system("cls");
return "上挂";
}else if(choose==2&&flag[2][x]==1){
flag[2][x]=0;
Color(6),Slowsay("下挂成功，一切恢复了往日的和平");
Color(8);
system("cls");
return "下挂";
}else{
}
return "";
}
//第八章：上挂状态的特殊判定（未完成）
//第九章：任意玩家的游戏界面
void gameboard(int x){
Color(2),Slowsay("请选择你本回合的动作");
Sleep(250);
Color(1);
cout<<"当前有"<<basic[0][x]<<"个玉；"<<basic[1][x]<<"个防；"<<basic[2][x]<<"个甩剑和"<<basic[3][x]<<"个闪"<<endl;
Color(6);
Sleep(250);
cout<<protect[1][x]<<"个护盾和"<<protect[2][x]<<"个钟"<<endl;
Sleep(250);
cout<<"对方有"<<protect[1][3-x]<<"个护盾和"<<protect[2][3-x]<<"个钟"<<endl;
Sleep(250);
Color(8),Slowsay("基础物资（玉、防、闪和甩剑）(0)");
Color(7),Slowsay("戳系(1)\n暴击系（下面也有马丁）(2)\n重拳系（上面也有马丁）(3)\n猪系(4)\n电系(5)\n斩系（基本没用）(6)\n狒狒系（有两种蕉）(7)\n洞系（有黑洞）(8)\n膜拜系(9)");
Color(5),Slowsay("其它道具（上下挂、举报、哈哈）(10)");
Color(3),Slowsay("防护道具（前台盾和前台钟）(11)");
Color(8);
}
//第十章：本回合伤害结算
void thisround(string s1,string s2){
bool isUp=false;
int timeup=5;
system("cls");
Color(2);
Slowsay("在本回合中");
Color(8);
Sleep(500);
cout<<"玩家1出了"<<s1<<endl;
Sleep(500);
cout<<"玩家2出了"<<s2<<endl;
//举报判定
if(s1=="举报"||s2=="举报"){
Color(3),Slowsay("某个玩家打出了举报，现在开始判定。");
Sleep(1000);
if(flag[2][1]==1){
Color(4);
Slowsay("玩家1上挂了，血量清零");
flag[1][1]=0;
isUp=true;
}if(flag[2][2]==1){
Color(4);
Slowsay("玩家2上挂了，血量清零");
flag[2][1]=0;
isUp=true;
}
if(isUp==false){
Color(2);
Slowsay("没有人上挂，游戏继续");
}
Color(8);
}
if(isUp==true){
Color(8);
Sleep(2000);
fiveSeconds();
return ;
}else{
Sleep(500);
}
//哈哈判定
if(flag[4][1]==3||flag[4][2]==3){
Color(3),Slowsay("某个玩家连续哈哈三次，现在开始判定。");
Sleep(1000);
if(flag[4][1]==3){
Color(4);
Slowsay("玩家1打出了3次，生命数-1");
flag[4][1]=0;
flag[1][1]--;
}if(flag[4][2]==3){
Color(4);
Slowsay("玩家2打出了3次，生命数-1");
flag[4][2]=0;
flag[1][2]--;
}
Color(8);
fiveSeconds();
return;
}
//伤害判定
fiveSeconds();
Color(8);
return ;
}
//第十一章：双人对决游戏面板
void game(){
int answer;
int timeup=5;
string s1,s2;
char choose;
while(1){
//过渡
system("cls");
Slowsay("请玩家2离开屏幕，输入任意键后按回车");
cin>>choose;
//玩家1
while(s1==""){
system("cls");
gameboard(1);
cin>>answer;
system("cls");
if(answer==0){
s1=__basic(1);
}else if(answer==10){
s1=__prop(1);
}else if(answer==11){
s1=__protect(1);
}else{
s1= __fight(1,answer);
}
}
//过渡
system("cls");
Slowsay("请玩家2来到屏幕，输入任意键后按回车");
cin>>choose;
//玩家2
while(s2==""){
system("cls");
gameboard(2);
cin>>answer;
system("cls");
if(answer==0){
s2=__basic(2);
}else if(answer==10){
s2=__prop(2);
}else if(answer==11){
s2=__protect(2);
}else{
s2=__fight(2,answer);
}
}
system("cls");
thisround(s1,s2);
//检测游戏是否结束
if(flag[2][1]&&flag[2][2]){
system("cls");
Color(8);
Slowsay("两人同时上挂，本次游戏平局");
break;
}else if(flag[1][1]>=3&&flag[1][2]>=3){
system("cls");
Color(8);
Slowsay("每人不小于3条命，本次游戏平局");
break;
}else if(flag[1][1]==0&&flag[1][2]>0){
system("cls");
Color(8);
Slowsay("玩家1被打死");
break;
}else if(flag[1][1]>0&&flag[1][2]==0){
system("cls");
Color(8);
Slowsay("玩家2被打死");
break;
}
if(s1!="哈哈")flag[4][1]=0;
if(s2!="哈哈")flag[4][2]=0;
s1="";
s2="";
}
Color(5);
while(timeup--){
cout<<timeup+1<<"秒后回到主界面"<<endl;
Sleep(1000);
}
system("cls");
Color(8);
}
char choose;
//第十二章：主函数
int main(){
init();
while(1){
start_();
choose=_getch();
if(choose=='1'){
system("cls");
_story();
}else if(choose=='2'){
system("cls");
not_write();
}else if(choose=='3'){
Sleep(1000);
game();
init();
}else if(choose=='4'){
system("cls");
Color(2),Slowsay("goodbye");
Color(8);
break;
}
Color(8);
}
return 0;
}
/*
目标：
1：编写上挂状态的行动，可以选择加入到4~11章的函数中（前缀：编写攻击）
2：编写50+种攻击方式（0/10类）
3：编写游戏规则（选）
4：每回合的伤害判定。如：是否有伤害（bool），伤害大小，两位玩家的前台
*/