欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Lost in Translation

程序员文章站 2022-04-19 17:15:12
...

题目链接:http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11739

贪心思想,建立分层图,对于层次不同的结点,层次靠近源点的在前面,对于层次相同的结点,费用小的放前面

直接用priority_queue建立一个有层次的堆,然后不断更新费用

Lost in TranslationLost in Translation

#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;
}