#include<bits/stdc++.h> using namespace std; int n,k,m,s,t,c[102],g[102][102],f[102][102],u,v,d; int main(){ scanf("%d%d%d%d%d",&n,&k,&m,&s,&t); for(int i=1;i<=n;i)for(int j=1;j<=n;j)f[i][j]=21743822; for(int i=1;i<=n;++i)scanf("%d",&c[i]); for(int i=1;i<=k;i)for(int j=1;j<=k;j)scanf("%d",&g[i][j]); for(int i=1;i<=m;++i){ scanf("%d%d%d",&u,&v,&d); if(!g[c[v]][c[u]]&&c[v]!=c[u])f[u][v]=min(f[u][v],d); if(!g[c[u]][c[v]]&&c[v]!=c[u])f[v][u]=min(f[v][u],d); } if(c[s]==c[t]){puts("-1");return 0;} for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(i!=j)for(int k=1;k<=n;++k)if(j!=k&&i!=k)if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j]; if(f[s][t]==21743822)puts("-1"); else printf("%d",f[s][t]); return 0; }

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <string> using namespace std; int n,k,a[20],f[10010],ans,print[20]; const int inf = 0x7ffffff; void gengxin() { int i = 1; f[1] = 1; while (1) { f[i] = inf; for (int j = 1; j <= k && i - a[j] >= 0; j++) f[i] = min(f[i],f[i - a[j]] + 1); if (f[i] > n) break; i++; } i--; if (i > ans) { ans = i; for (int j = 1; j <= k; j++) print[j] = a[j]; } } void dfs(int depth,int minn) { if (depth > k) { gengxin(); return; } for (int i = minn + 1; i <= minn * n + 1; i++) { a[depth] = i; dfs(depth + 1,i); a[depth] = 0; } } int main() { scanf("%d%d",&n,&k); a[1] = 1; dfs(2,1); for (int i = 1; i <= k; i++) printf("%d ",print[i]); printf("\n"); printf("MAX=%d",ans); }