记录编号	347318	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-11-13 09:19:13	内存使用	0.00 MiB

#pragma inline_recursion(on)
#define pro __attribute__((optimize("-Os")))
#define _inline __attribute__((always_inline))
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
 
using namespace std;
#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
typedef long long lg;
 
namespace PROIO {
    const int L=1<<15,OUTL = 9000;
    char chout[OUTL],*pout=chout;
    char buf[L],*s = buf,*t = buf;
    pro inline char getc() {
        if(s==t) t=(s=buf)+fread(buf,1,L,stdin);
        return s==t ? EOF:*s++;
    }
    pro inline int read(int &x) {
        register bool flag = 0;register char c;
        while((c=getc())>'9'||c<'0') {
          if(c == '-') flag = 1;
          else if(c == EOF) return 0;
        }
        x = c-'0';
        while((c=getc())<='9'&&c>='0')
          x = ((x<<1)+(x<<3))+c-'0';
        if(flag) x = -x;
    }
    pro inline void out(int x) {
        if(!x)*pout++ = '0';
        int p=0;char buft[10];
        while(x) buft[++p] = x%10+'0',x /= 10;
        while(p) *pout++ = buft[p--];
        *pout ++ ='\n';
    }
    pro void end(){fwrite(chout,1,pout-chout,stdout);} 
}using PROIO::read;using PROIO::out;using PROIO::end;
 
#define Rep(i, x, y) for (register int i = (x), _ = (y); i <= _; ++i)

int n,m,k,s,t,x,y,v;
int o[105][106],c[200],a[200][200];
int inf = 12345678;

pro int MAIN() {
  FRE(culture);
  read(n);read(k);read(m);read(s);read(t);
  Rep(i,1,n) read(c[i]);
  Rep(i,1,k) Rep(j,1,k) read(o[i][j]);
  Rep(i,1,k) o[i][i] = 1;
  Rep(i,1,m) {read(x);read(y);read(v); a[x][y] = a[y][x] = v;}
  Rep(i,1,n) Rep(j,1,n) if(o[c[i]][c[j]] || a[i][j]==0) a[i][j] = inf; 
  //Rep(i,1,n)Rep(j,1,n)
  //cout<<i<<" "<<j <<" "<<a[i][j]<<endl; 
  Rep(k,1,n) Rep(i,1,n) if(k!=i) 
    Rep(j,1,n) if(j!=i && k!=j)
      a[i][j] = min(a[i][j],a[i][k]+a[k][j]); 
  t = a[s][t];
  if(t > inf-100) t = -1;
  cout << t;
}
 
int dott = MAIN();
 
int main(){;}