本文共 1096 字，大约阅读时间需要 3 分钟。

Problem D Lost in Translation

题意：

         给出一个图，从顶点开始（English），寻找 到每个点优先满足路径最短时的最小花费。

思路：

         所谓路径最短优先，其实就是 bfs 逐层搜索。若同层中有指向同一节点但花费不同的边，取最小即可。每搜完一层统计一遍 ans，给搜到的点打上 vis 标记即可。

代码：

const int maxn = 4505;int n,m;struct node{    int v,c,w;    node() {}    node(int _v,int _c,int _w)    {        v = _v;        c = _c;        w = _w;    }    bool operator < (const node &b)const    {        if(c==b.c)            return w>b.w;        return c>b.c;    }};vector
   
    G[maxn];map
    
     maple;priority_queue
     
       q;string a[105];int vis[maxn];int bfs(){    memset(vis,0,sizeof(vis));    q.push(node(0,0,0));    int res = 0;    while(!q.empty())    {        node now = q.top();        q.pop();        if(vis[now.v])            continue;        vis[now.v] = 1;        res += now.w;        for(int i=0;i
      
       >a[i];        maple[a[i]] = i;    }    for(int i=0;i
       
        >l>>r>>c;        G[maple[l]].push_back(node(maple[r],1,c));        G[maple[r]].push_back(node(maple[l],1,c));    }    int ans=bfs();    if(ans==-1)        puts("Impossible");    else        printf("%d\n",ans);    return 0;}
       
      
     
    
   

转载地址：http://rpali.baihongyu.com/