题目描述

题目大意：

给定一张无向图，第一个人从点1出发每走一条边消耗A，第二个人从点2出发每走一条边消耗B，两个人相遇后一起走每走一条边消耗C，两个人到达点n的最小花销。

题目分析：

水题 分别从点1、点2、点n出发BFS一遍，预处理出每个点到点1、点2、点n的最短路，然后枚举两人相遇的点，计算消耗之和即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int c1,c2,c3;
int tot;
int next[100400],to[100400],head[100400];
void add(int x,int y)
{
    next[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
int a[100400];
int b[100400];
int c[100400];
bool book[100400];
void bfs(int x,int dis[])
{
    queue<int>q;
    memset(book,false,sizeof book);
    q.push(x);
    book[x]=1;
    dis[x]=0;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        for(int i=head[nmp];i;i=next[i])
            if(!book[to[i]])
            {
                dis[to[i]]=dis[nmp]+1;
                q.push(to[i]);
                book[to[i]]=1;
            }
    }
 
}
int main()
{
    scanf("%d%d%d%d%d",&c1,&c2,&c3,&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    bfs(1,a);
    bfs(2,b);
    bfs(n,c);
    long long ans=0x7f7f7f7f;
    for(int i=1;i<=n;i++)
        ans=min(ans,(long long)c1*a[i]+c2*b[i]+c3*c[i]);
    printf("%lld",ans);
    return 0;
}