首页 > 代码库 > Tyvj 1221 微子危机——战略
Tyvj 1221 微子危机——战略
背景
№.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 1001using 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 = 0,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 = 1;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 = 0;i < mx;i++) d[i] = 1000000000;}void dij(int s){ d[s]=0; orz tmp; tmp.d=0,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 = 0;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 = 0; for(int i = 1;i <= n;i++){ if(i == m) continue; if(d[i] >= 1000000000){ cout<<"Sth wrong."<<endl; return 0; } ans+=d[i]; } cout<<ans<<" M(s) are needed."<<endl; return 0;}
Tyvj 1221 微子危机——战略
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。