P1078

恰同学少年，凤华正茂；数风流人物，还看今朝。 / 2024-11-05 / 原文

然而题单里就是有这题……
dij，照亮世界！

#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t,a[105][105],wen[105];
int d[100005];
bool vis[100005];
int qi,mo,f;
inline int read(){int x=0;char ch=getchar();while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x;}
struct Edge{
    int v,w;
    Edge(int _v=0,int _w=0){v=_v,w=_w;}
};
vector<Edge>e[1005];
vector<int>di[1005];
struct Node{
    int v,w;
    Node(int _v=0,int _w=0){v=_v,w=_w;}
    bool operator <(const Node &n) const{
        return w>n.w;
    }
};
priority_queue<Node>q;
int x;
bool kx(int x,int y){
    for(int j=0;j<di[y].size();j++){
     	if(di[y][j]==x)return false;
     }
     return true;
}
void dijkstra()
{
    d[s]=0;
    q.push(Node(1,0));
    while(!q.empty()){
       	int x=q.top().v;
       	q.pop();
       	if(vis[x])continue;
       	vis[x]=true;
       	for(int i=0;i<e[x].size();i++) {
			int v=e[x][i].v;
       	  	int w=e[x][i].w;
       	  	if(kx(wen[x],wen[v]))	{
       	  	    if(d[v]>d[x]+w){
       	  	 		d[v]=d[x]+w;
       	  	 	 	q.push(Node(v,d[v]));
        		}
            }
            else continue;
       }
   }
}
int main(){
    n=read();k=read(); m=read(); s=read();t=read();	
    for(int i=1;i<=n;i++)wen[i]=read();
    for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
      		x=read();
      		if(x==1)di[i].push_back(j);
      		a[i][j]=x;
      	}
	}
    for(int j=1;j<=m;j++){
       	cin>>qi>>mo>>f;
       	if(a[mo][qi]==0)e[qi].push_back(Edge(mo,f));
       	if(a[qi][mo]==0)e[mo].push_back(Edge(qi,f));
    }
    memset(d,0x3f3f3f3f,sizeof(d));
    dijkstra();
    if(vis[t]&&wen[t]!=wen[s])cout<<d[t];
    else cout<<"-1";
    return 0;
}