记录编号	535325	评测结果	AAAAAAAWTTW
题目名称	[USACO 3.2] 香甜的黄油	最终得分	63
用户昵称	tat	是否通过	未通过
代码语言	C++	运行时间	3.897 s
提交时间	2019-07-04 16:29:33	内存使用	18.58 MiB

    #include <bits/stdc++.h>
    using namespace std;
    #define MA 100000
    #define ll long long
    ll dis[801][801]={0};
    struct ways{
    	int f;
    	int t;
    	int d;
    }w[1450];
    ll m[801]={0},maa=MA;
    int main(int argc, char** argv) {
    	freopen("butter.in","r",stdin);
    	freopen("butter.out","w",stdout);
        int n,p,c;
        cin>>n>>p>>c;
        for(int i=1;i<=n;i++){
        	int e;
        	cin>>e;
            m[e]++; 
        }
        for(int i=1;i<=c;i++){
        	int aa,bb,cc;
        	scanf("%d %d %d\n",&aa,&bb,&cc);
        	w[i].f=aa;
    		w[i].t=bb;
    		w[i].d=cc;
        }
        for(int k=1;k<=p;k++){
        	for(int j=1;j<=p;j++){
        		dis[k][j]=MA;
        	}
        	dis[k][k]=0;
        	for(int i=1;i<=p-1;i++){
        		for(int j=1;j<=c;j++){
        			if(dis[k][w[j].f]+w[j].d<dis[k][w[j].t]){
        				dis[k][w[j].t]=dis[k][w[j].f]+w[j].d;
        			}
        			else if(dis[k][w[j].t]+w[j].d<dis[k][w[j].f]){
        				dis[k][w[j].f]=dis[k][w[j].t]+w[j].d;
        			}
        		}
        	}
        	ll sum=0;
        	for(int i=1;i<=p;i++){
        		sum+=m[i]*dis[k][i];
        	}
        	if(sum<maa)maa=sum;
        //	cout<<sum<<' ';
        }
        cout<<maa;
    	return 0;
    }