Day4-T3
原题目
吉儿是一家古董店的老板娘,由于她经营有道,小店开得红红火火。昨天,吉儿无意之中得到了散 落民间几百年的珍宝——月亮之眼。吉儿深知“月亮之眼”价值连城:它是由许多珍珠相连而成的,工 匠们用金线连接珍珠,每根金线连接两个珍珠;同时又对每根金线染上两种颜色,一半染成银白色,一 半染成黛黑色。由于吉儿自小熟读古籍,所以还晓得“月亮之眼”的神秘传说:“月亮之眼”原是一个 古代寺庙的宝物,原本是挂在佛堂的一根顶梁柱上的,整个宝物垂直悬挂,所有珍珠排成一线,且都镶嵌在柱子里,而每一根金线又都是绷紧的,并且金线的银白色一端始终在黛黑色一端的上方;然而,在 一个月圆之夜,“月亮之眼”突然从柱里飞出,掉落下来,宝物本身完好无损,只是僧侣们再也无法以 原样把“月亮之眼”嵌入柱子中了。吉儿望着这个神秘的宝物,回忆着童年读到的传说,顿时萌发出恢 复“月亮之眼”的冲动,但是摆弄了几天依旧没有成功。
为了把“月亮之眼”还原,吉尔拜访了 P 个僧侣,每个僧侣根据自己的回忆告诉给了一些有关的信 息,主要是描述某两个珍珠之间的距离。
例如根据回忆,1 号珍珠到 5 号珍珠的距离是 10,其中 1 号这头是银白色金线,5 号这头是黛黑色 金线。
你要设计一个程序,对于给定的“月亮之眼”进行周密分析,然后给出这串宝物几百年前嵌在佛堂 顶梁柱上的排列模样(各个珍珠在顶梁柱上的位置),珍珠的大小忽略不计。
第一行有两个整数 N 和 P,其中 N 表示宝物中的珍珠个数,P 表示有 P 个僧侣的句子,对金线的一些描述; 以下 P 行描述珍珠连接情况:第 i+1 行有三个整数,Ri1,Ri2,Li。其中 Ri1 表示第 i 根金线的银白色一 端连接的珍珠序号;Ri2 表示第 i 根金线的黛黑色一端连接的珍珠序号;Li 表示第 i 根金线的长度。
输出文件共 N 行: 第 i 行一个整数 S,它表示标号为 i 的珍珠在顶梁柱上距离最高位置珍珠的距离。
若无解则输出仅一行,包含一个整数“-1”。
S1:
Input:
Output:
Describe:图论,就是求权值
code:
#include<bits/stdc++.h>
#define INF 214748364
#define eps 1e-9
#define rep1(a,b) for(register int i=(a);i<=(b);i++)
#define rep2(a,b) for(register int j=(a);j<=(b);j++)
using namespace std;
long long dis[255][255],g,n,p,x,y,z; //dis[i][j]表示 i->j 的最短路
bool flg;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline double read2(){
double X=0,Y=1.0;int w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=X*10+(ch^48),ch=getchar();
ch=getchar();
while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();
return w?-X:X;
}
inline void Floyd(){ //Floyd
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(i!=j&&j!=k&&i!=k)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
inline void write(int x){
if(x<0){putchar('-');write(-x);return;}
if(x/10) write(x/10);
putchar(x%10+'0');
}
int main(){
// freopen("mooneye.in","r",stdin);
// freopen("mooneye.out","w",stdout);
n=read(),p=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=0x7fffff,dis[i][i]=0; //memset
for(int i=1;i<=p;i++)x=read(),y=read(),z=read(),dis[x][y]=z,dis[y][x]=-z; //建边及反建边 [值为负]
Floyd();
for(int i=1;i<=n;i++){
flg=1;
for(int j=1;j<=n;j++)
if(dis[i][j]<0) //不在某一个点上,即非根节点
{
flg=0; //退出循环
break;
}
if(flg)g=i; //存储根节点
}
if(!g)cout<<-1,exit(0); //找不到根节点
for(int i=1;i<=n;i++)if(dis[g][i]==0x7fffff){cout<<-1;return 0;} //无边
for(int i=1;i<=n;i++)write(dis[g][i]),puts("");return 0; //输出
}
最新文章
- ubuntu系统下,gsl 库链接问题 -undefined reference to `cblas_xxx`
- Leetcode 94. Binary Tree Inorder Traversal
- 使用EF Oracle实现DevExpress绑定大数据的ServerMode模式
- nginx环境下配置nagios-关于start_perl_cgi.sh
- Java swing项目-图书管理系统(swing+mysql+jdbc)
- C/C++ 中长度为0的数组
- YYKit之YYModel
- word中几个好用的宏代码(立方米上标、关闭样式自动更新、删除无效样式、表格加粗边框、宋体引号)
- RTSP,RTP,RTCP的区别
- Struts2实现国际化
- Java中ArrayList与LinkedList的区别
- Linux显示文件和目录的详细资料
- 第二届强网杯部分writeup
- C# Emgu 类型转换
- mysql &; sqlserver语法差异
- AsyncHttpClient使用
- LeetCode算法题详解之两个数组的交集
- 初识CPU卡、SAM卡/CPU卡简介、SAM卡简介 【转】
- 出现“error LNK1169: 找到一个或多个多重定义的符号”的原因
- nginx补丁格式说明(CVE-2016-4450为例)
热门文章
- Windows的本地时间(LocalTime)、系统时间(SystemTime)、格林威治时间(UTC-Time)、文件时间(FileTime)之间的转换
- UniGUI 之UniDBGrid(05)
- ubuntu 14 双击会自动删除文本
- js通过cookie对两个没有关系的jsp页面进行传值
- UISearchBar设置背景色
- scrapy(创建scrapy工程)报错:“ ImportError:DLL load failed:找不到指定的模块”
- OPC DA通讯 KEP6.4 DCOM 配置脚本
- 第1节 kafka消息队列:2、kafka的架构介绍以及基本组件模型介绍
- 题解 LG P2264
- struts2--action请求与Action类