本文主要是介绍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];// + 此前的 + 这次的elsedij[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;
}
这篇关于Codeforces Round 918 (Div. 4)G题二维dijkstra的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!