Tyvj 1221 微子危机——战略
2024-09-05 15:56:22
背景
№.3
Summer联盟战前兵力战略转移。
Summer联盟战前兵力战略转移。
描述
Summer的兵力分布在各个星球上,现在需要把他们全部转移到某个星球上。
Summer一共拥有N个星球(1~N),你要把这N个星球上的兵力转到第M个星球上。本来每个星球之间都有星际轨道连接,但Guiolk监视了某些轨道,我们一但走上这些轨道,有可能受到他的攻击。为了安全,Summer不会走被监视的轨道。于是,只有L个星际轨道是被批准通过的。Summer的国防部想统计一下所需的最短路程(即每个星球到第M星球的最短路程总和,单位:M PS:'M'不是米)。
Summer一共拥有N个星球(1~N),你要把这N个星球上的兵力转到第M个星球上。本来每个星球之间都有星际轨道连接,但Guiolk监视了某些轨道,我们一但走上这些轨道,有可能受到他的攻击。为了安全,Summer不会走被监视的轨道。于是,只有L个星际轨道是被批准通过的。Summer的国防部想统计一下所需的最短路程(即每个星球到第M星球的最短路程总和,单位:M PS:'M'不是米)。
输入格式
第一行有三个正整数,N,M,L(分别如题目描述)接下来L行,为被批准通行的轨道。每行有三个整数:a,b,c,表示第a个星球和第b个星球之间的轨道长cM(有重复)。
输出格式
如果所有星球上的兵力能全部集中到第M个星球,则输出: 最短路程和+“ M(s) are needed.”如果某个星球的兵力不能到达第M个星球,则输出“Sth wrong.”。
测试样例1
输入
【样例输入1】
5 3 6
1 2 1
1 3 3
2 3 1
4 1 5
4 5 2
5 1 2
【样例输入2】
5 3 4
1 2 1
1 3 3
2 3 1
5 1 2
输出
【样例输出1】
13 M(s) are needed.
【样例输出2】
Sth wrong.
备注
对于30%的数据,1≤N≤20 , L≤200
对于80%的数据,1≤N≤600 , L≤180000
对于100%的数据,1≤N≤1000 , 1≤M≤N , L≤500000, 1≤a,b≤N , 0≤c≤10000。
2010年广州市第二中学初二第二次测试第三题。
对于80%的数据,1≤N≤600 , L≤180000
对于100%的数据,1≤N≤1000 , 1≤M≤N , L≤500000, 1≤a,b≤N , 0≤c≤10000。
2010年广州市第二中学初二第二次测试第三题。
思路:
堆优化dij裸求最短路
代码:
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define mx 1001 using namespace std;
struct orz
{
int d,p;
friend bool operator <(orz a,orz b) {return a.d>b.d;}//堆和set里面都只有小于号,所以要用小根堆的话要将<重定向为>
};
struct Edge{
int to;
int w;
};
priority_queue < orz > ss;
int flag = ,v[mx],d[mx],n,m,l;
vector<Edge> edge[mx];
void input(){
cin>>n>>m>>l;
int u,v,wei;
Edge test;
for(int i = ;i <= l;i++){
scanf("%d%d%d",&u,&v,&wei);
test.to = v;
test.w = wei;
edge[u].push_back(test);
test.to = u;
edge[v].push_back(test);
}
for(int i = ;i < mx;i++) d[i] = ;
}
void dij(int s)
{ d[s]=;
orz tmp;
tmp.d=,tmp.p=s;
ss.push(tmp);
flag++;
int x,dd;
Edge j;
while (!ss.empty())//不能只做n次,要一直做到堆空
{
tmp=ss.top();
ss.pop();
x=tmp.p,dd=tmp.d;
if (v[x]==flag) continue;//这里一定要判断!!!
v[x]=flag;
for (int i = ;i < edge[x].size();i++){ j = edge[x][i];
if (d[j.to]>dd+j.w)
{
d[j.to]=dd+j.w;
tmp.d=dd+j.w,tmp.p=j.to;
ss.push(tmp);
}
} }
}
int main(){
input();
dij(m);
int ans = ;
for(int i = ;i <= n;i++){
if(i == m) continue;
if(d[i] >= ){
cout<<"Sth wrong."<<endl;
return ;
}
ans+=d[i];
}
cout<<ans<<" M(s) are needed."<<endl;
return ;
}
最新文章
- img的onerror事件(瑕疵+解决办法)【转】
- String和string的区别
- 导出程序界面(UI)到图片
- 【JAVA - SSM】之MyBatis与原生JDBC、Hibernate访问数据库的比较
- 最详细的 HTTPS 科普扫盲帖
- Tkinter隐藏窗口再让他显示出来的例子
- 某大神C#框架后台发送信息的查找及破解
- Fragment(四)Fragment生命周期分析(转)
- 大三小学期 Android开发的一些经验
- docker-maven-plugin插件设置Docker的buildArgs
- 利用Python生成GIF动图
- Javascript中表达式和语句的区别
- jquery基础学习之AJAX篇(五)
- 二叉查找树迭代器 &#183; Binary Search Tree Iterator
- VS Code 终端窗口无法输入命令的解决方案
- 孙鑫VC++视频教程(1-20课全)
- Ubuntu下找不到php5,phpize等可执行程序的解决办法
- 洛谷P3941入阵曲
- TCP/IP网络协议攻击
- JavaScript设置获取和设置属性的方法