考察:连通图,最短路径;
题意:第一行输入,第一个是n个城市,m个通路,再输入一个数为query行查询,检查每一行的,按顺序判断,从0号城市开始最后要回到0号城市,检验是否连通,每个城市只能去一次,每个城市都要去;
收获:
1.#include
2.fill,给容器赋值,在头文件#include里面;
格式:fill(a,a+length,value);
3.连通图的设置,设置一个二维数组edge[n][m]=edge[m][n]=value,连通两个city并加权;
代码:
#include#include #include using namespace std; int main(){ int edge[201][201]={0},path[202],isshown[201]; int n,m,a,b,c,query,num,legalnum,cost,flag; int mincost=INT_MAX,minnum; cin>>n>>m; for(int i=0;i >a>>b>>c; edge[a][b]=edge[b][a]=c;//连通图; } cin>>query; for(int i=1;i<=query;i++){ fill(isshown,isshown+n+1,0);//复原,为下一行输入做准备,; path[n+1]=flag=cost=0;;//复原,为下一行输入做准备; cin>>num;//输入查询网红点个数; for(int j=1;j<=num;j++){//等下以i作为最小的序号,所以最好是从1开始; cin>>path[j]; if(isshown[path[j]]==1){ isshown[0]=1;//这里不能直接break或者continue,缓冲区的输入还没输入完成,现在先标记,后面再判断就好了,不要急着退出; } isshown[path[j]]=1;//break只能退出break所在的那个循环; } if(num!=n||isshown[0]==1){//这个是攻略城市不足或者城市重复的情况; continue;//退出到下一行的输入; } for(int k=1;k<=num+1;k++){//+1是因为他最后要回到家,所以回家也要有路;path顺序储存顺序,for顺序查找; if(edge[path[k-1]][path[k]]==0){ flag=1; break; } cost+=edge[path[k-1]][path[k]]; } if(!flag){ legalnum++; if(mincost>cost){ swap(cost,mincost); minnum=i; } } } cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)