https://oj.dgzx.net/front/problem/ToProblemDetailBlank/1043

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
struct edge
{
	int to;
	int w;
};
vector<edge> head[1001];
priority_queue<edge> q;
bool operator <(const edge &a,const edge &b){
	return a.w>b.w;
} 
int dis[1001];
bool vis[1001];
int main() 
{
	int n,w;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>w;
			if(w) head[i].push_back({j,w});	 
		}
	}
	for(int i=1;i<=n;i++) dis[i]=INF;
	int x,y;
	cin>>x>>y;
	vis[x]=true;
	dis[x]=0;
	for(int i=1;i<head[x].size();i++)
	{
		int u=head[x][i].to;//与起点直连点 
		dis[u]=head[x][i].w;//因为直连，dis[u]等于x,u边权值 
		q.push({u,dis[u]});//入队 
	}
	while(!q.empty())//有未更改点 
	{
		//出队 
		edge d=q.top();
		q.pop();
		int u=d.to;
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=1;i<head[u].size();i++)
		{
			int v=head[u][i].to;//其边另一点 
			if(!vis[v]&&dis[u]+head[u][i].w<dis[v])//head[u][i].w u与v距离 
			{
				dis[v]=dis[u]+head[u][i].w;//更改 
				q.push({v,dis[v]});	//入队 
			}	
		} 
	}
	cout<<dis[y];
	return 0;
}