首页 > 代码库 > Tyvj 1221 微子危机——战略

Tyvj 1221 微子危机——战略

2024-08-10 22:34:04   225人阅读

背景

№.3
Summer联盟战前兵力战略转移。

描述

Summer的兵力分布在各个星球上，现在需要把他们全部转移到某个星球上。
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年广州市第二中学初二第二次测试第三题。
 
思路：
堆优化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 微子危机——战略


联系
我们