已经讲过SPFA了吧。。。。

题目描述

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入输出格式

输入格式

第一行: 三个数：奶牛数N，牧场数（2<=P<=800），牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的。

输出格式

一行输出奶牛必须行走的最小的距离和。

INPUT & OUTPUT’s examples

Input’s eg #1

Output’s eg #1

说明

           P2  
P1 @--1--@ C1
         |
         | 
       5  7  3
         |   
         |     C3
       C2 @--5--@
          P3    P4

分析

与之前讲过的几道模板不同，本题对于SPFA求解之后的最短路还需要进行进一步处理。

由于我们需要找出使所有牛到达的路程和最短的牧场，所以枚举每一个点，跑一遍SPFA，然后用一个变量存一下它的路径长度。

最后取最小值即可。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<queue>
#include<iostream> 
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* consts */
const int MAXN = 3e3+10;
const int inf = 0x7f7f7f7f;
/* defintios */
struct Node{
    int next,to;
    int dis;
};
Node Butter[MAXN];
int cows[MAXN*MAXN],n,m,p,dist[MAXN];
int head[MAXN],cnt,sum,ans=inf;
bool visited[MAXN];
queue<int>Q;
/* functions */
inline void Add_Edge(int from,int to,int color){
    Butter[++cnt].next=head[from];
    Butter[cnt].to=to;
    Butter[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[k]=0;
    Q.push(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop();
        visited[first]=false;
        for(int i=head[first];i;i=Butter[i].next){
            if(dist[Butter[i].to]>dist[first]+Butter[i].dis){
                dist[Butter[i].to]=dist[first]+Butter[i].dis;
                if(!visited[Butter[i].to]){
                    visited[Butter[i].to]=true;
                    Q.push(Butter[i].to);
                }
            }
        }
    }
}
int main(int argc,char *argv[]){
    int a,b,c;
    cin>>p>>n>>m;
    for(int i=1;i<=p;i++)cin>>cows[i];
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        Add_Edge(a,b,c);
        Add_Edge(b,a,c);
    }
    for(int i=1;i<=n;i++){
        sum=0;
        SPFA(i);
        for(int j=1;j<=p;j++)sum+=dist[cows[j]];
        ans=min(ans,sum); 
    }
    cout<<ans<<endl;
    return 0;
}

洛谷P1828题解