迪克斯特拉 算法可以以优秀的时间复杂度解决

#include<bits/stdc++.h>
#define INF 0x3fffffff
#define N 20005
using namespace std;
int s[10];
int d[10]={0,2,6,4,8,6,10,14};
int a,b,c;
struct edge
{
	int v,w;
};
vector<edge>g[N];
int vis[N];
int dis[N];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void dijkstra()
{
	fill(dis,dis+N,INF);
	memset(vis,0,sizeof vis);
	dis[a]=0;
	q.push({0,a});
	
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:g[u])
		{
			int v=i.v;
			int w=i.w;
			int len=dis[u]+(s[w]?(d[w]/2):d[w]);
			if(len<dis[v])
			{
				dis[v]=len;
				q.push({len,v});
			}
		}
	}
}

int main()
{
	for(int i=1;i<=7;i++)
		cin>>s[i];
	cin>>a>>b>>c;
	for(int i=1;i<=c;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dijkstra();
	cout<<dis[b];
	return 0;
}