Codeforces Round 918 (Div. 4)G题二维dijkstra

（读本文前需知dijkstra求最短路算法）?

目录

目标：

难点：

本题方法：

AC代码：

---

题目：Problem - G - Codeforces

目标：

本题是求1到n的最短路

难点：

本题的路径长度（即权值）是距离*自行车slowness

这就使得最短路很难求，比如第一个样例，就是绕到城市3选到slowness最小的自行车然后去终点最小

本题方法：

用ans[ i ]来表示城市 i 到终点n的最小长度? ?(很巧妙，看后面的变换去理解原因吧)

那么ans[1]就是答案

重点就是这个ans的变换了

从slowness最小的城市开始顺序dijkstra（可以求得该点到所有点的最短路）（多重dijkstra)，这也包括到终点n的最短路

（为什么从slowness最小的城市开始呢，是贪心，我不好证明，，举个小反例：3经过4，ans[3]先于ans[4]算好了，但是3其实经过4可以有更短的（这需要4的slowness更小），此时ans[3]是错的

（slowness和城市下标捆绑排序（用个结构体，写个重载<就可以））

最短路求完进行这些操作：

1.ans[i] = dis[n];     //先把自己到终点的距离存了，然后看有没有更短的

2.for(int j=1;j<=n;j++)    //遍历从1到n所有城市，看能否中转而有更短路径
{
                                //也可能到不了城市j,或者城市j的slowness更大，没
    if(dis[j]!=0&&ans[j]!=0)    //必要比（更大所以还没有求最短路，所以ans[j]为0）
        ans[i] = min(ans[i],dis[j]+ans[j]);
}

AC代码：

（与上面的i,j不对应，dijkstra用了优先级队列做优化）

#define ll long long
int n, m; 
struct dis_node//放堆里面比长度，但是想知道端点
{
	ll dis;
	int next;
	bool operator < (const dis_node& a)
	{
		return dis < a.dis;
	}
	dis_node(ll d,int n)
	{
		dis = d; next = n;
	}
};
class cmp
{
public:
	bool operator()(dis_node a, dis_node b)
	{
		return a.dis > b.dis;//
	}
};
void dijkstr(vector<set<int>>&arr, vector<vector<int>>&dis,int bike, int ori, vector<ll>&ans)
{
	priority_queue<dis_node, vector<dis_node>, cmp>heap;
	vector<ll>dij(n + 1);
	vector<int>barr(n+1);
	int cur = ori;
	while (1)
	{
		for (auto next : arr[cur])//该次点所有可走的
		{
			//next就是下一个点（邻接表
			if (dij[next] == 0)
				dij[next] = dij[cur] + bike * dis[cur][next];
								//      + 此前的 + 这次的
			else
				dij[next] = min(dij[next], dij[cur] + bike * dis[cur][next]);
			heap.push(dis_node(dij[next],next));
		}
		barr[cur] = 1;
		while (heap.size())
		{
			if (barr[heap.top().next] == 0)
				break;
			heap.pop();
		}
		if (heap.size() == 0)break;
		cur = heap.top().next;
		heap.pop();
	}
	//对ans做调整
	ans[ori] = dij[n];
	for (int i = 1; i <= n; i++)
	{
		if (dij[i] != 0&& ans[i] != 0)
		{
			ans[ori] = min(dij[i] + ans[i], ans[ori]);
		}
	}
}
struct s_i
{
	int slow, i;
	const bool operator<(const s_i& b)
	{
		return slow < b.slow;
	}
};
void solve()
{
	cin >> n >> m;
	vector<set<int>>arr(n + 1);
	vector<ll>ans(n + 1);
	ans[1] = 0;
	vector<vector<int>>dis(n + 1, vector<int>(n + 1));
	vector<s_i>slowness(n+1);
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		arr[u].insert(v);
		arr[v].insert(u);//
		if (dis[u][v] == 0)
		{
			dis[u][v] = w;
			dis[v][u] = w;
		}
		else
		{
			dis[u][v] = min(dis[u][v], w);
			dis[v][u] = min(dis[v][u], w);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> slowness[i].slow;
		slowness[i].i = i;
	}

	//sort(slowness.begin()+1, slowness.end());
	for(int i=1;i<=n;i++)
		dijkstr(arr, dis, slowness[i].slow, slowness[i].i,ans);
	cout << ans[1] << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}