首页 > 其他分享 >牛的旅行 luoguP1522 多余的换行造成的影响

牛的旅行 luoguP1522 多余的换行造成的影响

时间：2023-08-19 12:34:11浏览次数：34  
标签：旅行 换行 ++ tp int while luoguP1522 dis getchar

牛的旅行

#include<bits/stdc++.h>
using namespace std;
int read(){
    int f=1,x=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
    return f*x;
}
int n,cnt,hd[160],vis[160];
double dis[160],B[160],D[160];
char c;
bool b[160];
struct plac{
    int x,y;
}a[160];
struct node{
    int to,nxt;
    double l;
}edge[50000];
double dist(int xa,int xb,int ya,int yb){
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
void add(int u,int v){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].nxt=hd[u];
    edge[cnt].l=dist(a[u].x,a[v].x,a[u].y,a[v].y);
    hd[u]=cnt;
}
void dfs(int u,int col){
    if(vis[u]) return;
    vis[u]=col;
    for(int i=hd[u];i;i=edge[i].nxt) dfs(edge[i].to,col);
}
struct nod{
    double l;
    int d;
    bool operator<(const nod &w)const{
        return l>w.l;
    }
};
priority_queue<nod> q;
void dij(int st){
    for(int i=1;i<=n;i++) dis[i]=1000000000;
    memset(b,0,sizeof(b));
    q.push((nod){0,st});
    dis[st]=0;
    while(!q.empty()){
        int tp=q.top().d;
        q.pop();
        if(b[tp]) continue;
        b[tp]=1;
        for(int i=hd[tp];i;i=edge[i].nxt){
            int v=edge[i].to;
            double w=edge[i].l;
            if(dis[v]>dis[tp]+edge[i].l){
                dis[v]=dis[tp]+edge[i].l;
                q.push((nod){dis[v],v});
            }
        }
    }
    int t;
    double mx=-1;
    for(int i=1;i<=n;i++){
        if(vis[i]==cnt) B[st]=max(B[st],dis[i]);
    }
    D[cnt]=max(D[cnt],B[st]);
}
double ans=2147483647;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
    }
    getchar();
    for(int i=1;i<=n;i++){
        int j = 0;
        while(c = getchar()){
            if(c != '0' && c != '1') break;
            ++j;
            if(c == '1'){
                add(i,j);
                cout<<"i,j "<<i<<" "<<j<<endl;
            } 
        }
        getchar();
    }
    cnt=0;//可回收垃圾 
    for(int i=1;i<=n;i++){
        if(!vis[i]){//这个点在一个新的集合 
            dfs(i,++cnt);//把这个集合里所有的点找出来染色 
            for(int j=1;j<=n;j++){
                if(vis[j]==cnt) dij(j);//这个集合里每个点都当一次与外部连接的点 
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i]==vis[j]) continue;//一个集合内就不连了 
            ans=min(ans,max(dist(a[i].x,a[j].x,a[i].y,a[j].y)+B[i]+B[j],max(D[vis[i]],D[vis[j]])));//答案就是所有可连接的点中连线的长度再加上两个牧场原来与这些点连接的最长长度（还有两个联通块的直径）
        }
    }
    printf("%.6lf",ans);
    return 0;
}

wa代码：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int f=1,x=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
    return f*x;
}
int n,cnt,hd[160],vis[160];
double dis[160],B[160],D[160];
char c;
bool b[160];
struct plac{
    int x,y;
}a[160];
struct node{
    int to,nxt;
    double l;
}edge[50000];
double dist(int xa,int xb,int ya,int yb){
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
void add(int u,int v){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].nxt=hd[u];
    edge[cnt].l=dist(a[u].x,a[v].x,a[u].y,a[v].y);
    hd[u]=cnt;
}
void dfs(int u,int col){
    if(vis[u]) return;
    vis[u]=col;
    for(int i=hd[u];i;i=edge[i].nxt) dfs(edge[i].to,col);
}
struct nod{
    double l;
    int d;
    bool operator<(const nod &w)const{
        return l>w.l;
    }
};
priority_queue<nod> q;
void dij(int st){
    for(int i=1;i<=n;i++) dis[i]=1000000000;
    memset(b,0,sizeof(b));
    q.push(nod{0,st});
    dis[st]=0;
    while(!q.empty()){
        int tp=q.top().d;
        q.pop();
        if(b[tp]) continue;
        b[tp]=1;
        for(int i=hd[tp];i;i=edge[i].nxt){
            int v=edge[i].to;
            double w=edge[i].l;
            if(dis[v]>dis[tp]+edge[i].l){
                dis[v]=dis[tp]+edge[i].l;
                q.push(nod{dis[v],v});
            }
        }
    }
    int t;
    double mx=-1;
    for(int i=1;i<=n;i++){
        if(vis[i]==cnt) B[st]=max(B[st],dis[i]);
    }
    D[cnt]=max(D[cnt],B[st]);
}
double ans=2147483647;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++){
            c=getchar();
            if(c=='\n') continue;
            if(c=='1') add(i,j);//连接两个点 
        }
    }
    cnt=0;//可回收垃圾 
    for(int i=1;i<=n;i++){
        if(!vis[i]){//这个点在一个新的集合 
            dfs(i,++cnt);//把这个集合里所有的点找出来染色 
            for(int j=1;j<=n;j++){
                if(vis[j]==cnt) dij(j);//这个集合里每个点都当一次与外部连接的点 
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i]==vis[j]) continue;//一个集合内就不连了 
            ans=min(ans,max(dist(a[i].x,a[j].x,a[i].y,a[j].y)+B[i]+B[j],max(D[vis[i]],D[vis[j]])));//答案就是所有可连接的点中连线的长度再加上两个牧场原来与这些点连接的最长长度（还有两个联通块的直径）
        }
    }
    printf("%.6lf",ans);
    return 0;
}

正行读入：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int f=1,x=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
    return f*x;
}
int n,cnt,hd[160],vis[160];
double dis[160],B[160],D[160];
char c;
bool b[160];
string s;
struct plac{
    int x,y;
}a[160];
struct node{
    int to,nxt;
    double l;
}edge[50000];
double dist(int xa,int xb,int ya,int yb){
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
void add(int u,int v){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].nxt=hd[u];
    edge[cnt].l=dist(a[u].x,a[v].x,a[u].y,a[v].y);
    hd[u]=cnt;
}
void dfs(int u,int col){
    if(vis[u]) return;
    vis[u]=col;
    for(int i=hd[u];i;i=edge[i].nxt) dfs(edge[i].to,col);
}
struct nod{
    double l;
    int d;
    bool operator<(const nod &w)const{
        return l>w.l;
    }
};
priority_queue<nod> q;
void dij(int st){
    for(int i=1;i<=n;i++) dis[i]=1000000000;
    memset(b,0,sizeof(b));
    q.push((nod){0,st});
    dis[st]=0;
    while(!q.empty()){
        int tp=q.top().d;
        q.pop();
        if(b[tp]) continue;
        b[tp]=1;
        for(int i=hd[tp];i;i=edge[i].nxt){
            int v=edge[i].to;
            double w=edge[i].l;
            if(dis[v]>dis[tp]+edge[i].l){
                dis[v]=dis[tp]+edge[i].l;
                q.push((nod){dis[v],v});
            }
        }
    }
    int t;
    double mx=-1;
    for(int i=1;i<=n;i++){
        if(vis[i]==cnt) B[st]=max(B[st],dis[i]);
    }
    D[cnt]=max(D[cnt],B[st]);
}
double ans=2147483647;
int main(){
//    freopen("travel4.in","r",stdin); 
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
    }
    getchar();//windows下多余的符号 
    for(int i = 1; i <= n; i++){
        getline(cin,s);
        for(int j = 1; j <= n; j++)
            if(s[j-1] == '1') add(i,j);
    }
    cnt=0;//可回收垃圾 
    for(int i=1;i<=n;i++){
        if(!vis[i]){//这个点在一个新的集合 
            dfs(i,++cnt);//把这个集合里所有的点找出来染色 
            for(int j=1;j<=n;j++){
                if(vis[j]==cnt) dij(j);//这个集合里每个点都当一次与外部连接的点 
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i]==vis[j]) continue;//一个集合内就不连了 
            ans=min(ans,max(dist(a[i].x,a[j].x,a[i].y,a[j].y)+B[i]+B[j],max(D[vis[i]],D[vis[j]])));//答案就是所有可连接的点中连线的长度再加上两个牧场原来与这些点连接的最长长度（还有两个联通块的直径）
        }
    }
    printf("%.6lf",ans);
    return 0;
}

 

#include<bits/stdc++.h>using namespace std;int read(){int f=1,x=0; char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}return f*x;}int n,cnt,hd[160],vis[160];double dis[160],B[160],D[160];char c;bool b[160];string s;struct plac{int x,y;}a[160];struct node{int to,nxt;double l;}edge[50000];double dist(int xa,int xb,int ya,int yb){return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));}void add(int u,int v){cnt++;edge[cnt].to=v;edge[cnt].nxt=hd[u];edge[cnt].l=dist(a[u].x,a[v].x,a[u].y,a[v].y);hd[u]=cnt;}void dfs(int u,int col){if(vis[u]) return;vis[u]=col;for(int i=hd[u];i;i=edge[i].nxt) dfs(edge[i].to,col);}struct nod{double l;int d;bool operator<(const nod &w)const{return l>w.l;}};priority_queue<nod> q;void dij(int st){for(int i=1;i<=n;i++) dis[i]=1000000000;memset(b,0,sizeof(b));q.push((nod){0,st});dis[st]=0;while(!q.empty()){int tp=q.top().d;q.pop();if(b[tp]) continue;b[tp]=1;for(int i=hd[tp];i;i=edge[i].nxt){int v=edge[i].to;double w=edge[i].l;if(dis[v]>dis[tp]+edge[i].l){dis[v]=dis[tp]+edge[i].l;q.push((nod){dis[v],v});}}}int t;double mx=-1;for(int i=1;i<=n;i++){if(vis[i]==cnt) B[st]=max(B[st],dis[i]);}D[cnt]=max(D[cnt],B[st]);}double ans=2147483647;int main(){//freopen("travel4.in","r",stdin); n=read();for(int i=1;i<=n;i++){a[i].x=read();a[i].y=read();}getchar();//windows下多余的符号 for(int i = 1; i <= n; i++){getline(cin,s);for(int j = 1; j <= n; j++)if(s[j-1] == '1') add(i,j);}cnt=0;//可回收垃圾 for(int i=1;i<=n;i++){if(!vis[i]){//这个点在一个新的集合 dfs(i,++cnt);//把这个集合里所有的点找出来染色 for(int j=1;j<=n;j++){if(vis[j]==cnt) dij(j);//这个集合里每个点都当一次与外部连接的点 }}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(vis[i]==vis[j]) continue;//一个集合内就不连了 ans=min(ans,max(dist(a[i].x,a[j].x,a[i].y,a[j].y)+B[i]+B[j],max(D[vis[i]],D[vis[j]])));//答案就是所有可连接的点中连线的长度再加上两个牧场原来与这些点连接的最长长度（还有两个联通块的直径）}}printf("%.6lf",ans);return 0;}

标签：旅行,换行,++,tp,int,while,luoguP1522,dis,getchar
From： https://www.cnblogs.com/caterpillor/p/17642322.html

相关文章

  • vim逗号替换为换行符
     %s/,/\r/g   %：表示在整个文件中进行操作。s/：表示替换的开始。,：表示要被替换的目标字符串，即逗号。/：分隔符，用于分隔目标字符串和替换字符串。\r：替换字符串，即回车符。/g：表示全局替换，即替换所有匹配到的逗号。......
  • 如何去除UNIX系統下文件中的换行符^M
        因操作系统的差异，在Windows系统编辑文件时的换行符是CRLF，而在Unix系统（包括AIX、LINUX）编辑文件时的换行符为LF，当把在Windows系统编辑的文件传送到Unix系统上后，查看文件会发现每行后面多了一个^M符号，这个有可能会导致在执行某些脚本时出现问题，那么该如何解决呢？1、当需要......
  • Apache HTTPd换行解析漏洞复现CVE-2017-15715
    ApacheHTTPd换行解析漏洞复现CVE-2017-15715漏洞利用漏洞利用条件Apache:2.4.0~2.4.29实际存到后端时的文件名可控漏洞利用方式bp中更改存放到后端的文件名假设原文件名为"evil.php"文件存放在网站根目录下evil.php的内容为:<?php@eval($_REQUEST[1]);?>操作:......
  • 旅行之前
    2023-08-1621:12:04星期三明天就要去济南，后天早上出发去南昌，四年没有出过门旅游了，终于可以出门了，虽然经历了很多不愉快.现在教资草草复习了科二，科一旅游结束后应该开始真题了，科三除了教案设计之类其他都复习过了；高代复习到了Jordan标准型，总算知道为什么要引入\(\lambda......
  • 東京の日帰り旅行
    これは私の二回目の東京の旅。前回は東京のシンボルの観光地を中心にした旅だったが、今回は日本の友達のお勧めでの旅だ。前回は目的地が多かったので慌ただしい旅だったが、今回は予定が少なかったので、足の向くままの旅だ。前回は日本語が上手な同僚の手伝いで団体の旅だった......
  • 人生で忘れられない旅行
    ――北海道の旅2014/5/7  三泊四日の北海道の旅は楽しかったので、細々とした思い出が時々頭に浮かんでくる。喜んでいた時があったし、道を迷っていた時もあったし、絶景にびっくりさせられた時もあったし、疲れて諦めようとした時もあった。様々な体験を含......
  • dp-双调欧几里德旅行商问题
    双调欧几里德旅行商问题目录双调欧几里德旅行商问题问题描述分析递推关系程序算法导论3rd-15.3问题描述平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）J.L.Bentley建议通过只考虑双调旅程(bitonictour)来简化问题,这种旅程即......
  • P1137 旅行计划
    \(P1137\)旅行计划这个题，我们根据题意是不是知道这个是一个\(DAG\)，我们需要计算的是以城市\(i\)为终点最多能够游览多少个城市；这个是不是也是在一个拓扑序上做一个简单的\(dp\)就行了，我们记录一下最大值即可；#include<bits/stdc++.h>usingnamespacestd;constintN=1......
  • git换行符
    问题假如其他人在Windows上编程，而你却在其他系统上，在这些情况下，你可能会遇到行尾结束符问题。这是因为Windows使用回车和换行两个字符来结束一行，而Mac和Linux只使用换行一个字符。虽然这是小问题，但它会极大地扰乱跨平台协作。在Windows平台上，git默认的core.autocrlf是true，......
  • 解决 Blazor 中因标签换行导致的行内元素空隙问题
    实践过不同前端框架的朋友应该都知道，对于同一个样式，在不同框架上的表现都会有不同，时时需要做“适配”，在Blazor上也不例外。在做AntDesignBlazor时就深有体会，因为我们是同步官方的样式，他们的样式只考虑了React上的实现，除非有人专门提PR，否则都不会特别考虑其他框架的实现。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99