Lost in Translation
程序员文章站
2022-04-19 17:15:12
...
题目链接:http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11739
贪心思想,建立分层图,对于层次不同的结点,层次靠近源点的在前面,对于层次相同的结点,费用小的放前面
直接用priority_queue建立一个有层次的堆,然后不断更新费用
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llt;
struct edge_t
{
int v,next;
llt cost;
edge_t(int a=0,llt b=0) {v=a;cost=b;}
}edge[10000];
int vertex[320];
int Ecnt;
struct qnode
{
int v,heaps;
llt cost;
qnode(int _v=0,int _heaps=0,llt _cost=0) {v=_v;heaps=_heaps;cost=_cost;}
bool operator < (const qnode &r)const
{
if(heaps!=r.heaps) return heaps>r.heaps;
return cost>r.cost;
}
};
void init_Graph()
{
Ecnt=1;
memset(vertex,0,sizeof(vertex));
}
void Build_edge(int a,int b,llt c)
{
edge[Ecnt].v=b;
edge[Ecnt].cost=c;
edge[Ecnt].next=vertex[a];
vertex[a]=Ecnt++;
}
bool vis[320];
void bfs(int s,int n)
{
llt fee=0;
int cnt=0;
memset(vis,false,sizeof(vis));
priority_queue<qnode> q;
while(!q.empty()) q.pop();
qnode tmp(0,0,0);
q.push(tmp);
while(!q.empty())
{
tmp=q.top();
q.pop();
int u=tmp.v;
int h=tmp.heaps;
if(vis[u]) continue;
vis[u]=true;
//printf("Have vis %d\n",u);
fee+=tmp.cost;
cnt++;
if(cnt==n+1) break;
for(int next=vertex[u];next;next=edge[next].next)
{
int to=edge[next].v,cost=edge[next].cost;
q.push(qnode(to,h+1,cost));
}
}
if(cnt==n+1) printf("%I64d\n",fee);
else printf("Impossible\n");
}
map<string,int> lau;
int main()
{
int n,m;
string tmp;
string a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
init_Graph();
lau.clear();
llt fee;
lau.insert(make_pair("English",0));
for(int i=1;i<=n;i++)
{
cin>>tmp;
lau.insert(make_pair(tmp,i));
}
for(int i=1;i<=m;i++)
{
cin>>a>>b>>fee;
Build_edge(lau[a],lau[b],fee);
Build_edge(lau[b],lau[a],fee);
}
bfs(0,n);
}
return 0;
}
推荐阅读
-
Lost connection to MySQL server during query的解决
-
Lost connection to MySQL server during query的解决
-
Fireworks教程-Lost RGB(图文)
-
上海超人气的网红甜品店 Lost Bakery上榜 BoboLEE第二
-
1416- Find the Lost Sock(异或运算) ZCMU
-
解决lost connection to mysql server at reading initial communication packet
-
解决lost connection to mysql server at reading initial communication packet
-
linux登录远程服务器及scp命令传输文件(ssh(Connection refused lost connection) 错误),及centos7.3防火墙操作
-
【递推】Ayoub and Lost Array
-
PHP get_html_translation_table()函数用法讲解