贵阳网站建设公司哪家好,用帝国软件做网站的心得,搜狗推广登录入口,怎么修改网站关键词Problem - C - Codeforces
目录
题意#xff1a;
思路#xff1a;
答疑#xff1a;
1.为什么反向做呢#xff1f;
2.为什么是到达点的剩余度数呢#xff1f;
3.相同路是否可以去重#xff0c;用个set#xff1f;
4.如果有多条路相同呢#xff1f;
参考代码
思路
答疑
1.为什么反向做呢
2.为什么是到达点的剩余度数呢
3.相同路是否可以去重用个set
4.如果有多条路相同呢
参考代码 题意
有向图。
从1走到n可以停一天去封某条路。返回 最优地封完后的 最坏情况。
样例3 思路
https://www.cnblogs.com/AWhiteWall/p/13158089.html参考佬的思路
方法
比如到 n点 有 3条路但是剩下两条比最优的一条要远十几天。那么不如用两天时间把这两条路给封掉。这是正向想的
所以干脆算最优时直接加上两天 取这几种的最小值即可。加的这两天就是 n 点的“剩余入度” ——————
所以我们反向建有向图反向dijktra每条路的距离天数为 1 加上 到此点的剩余度数。 答疑
1.为什么反向做呢
因为我们不要离谱长的边要直接封掉那么这些路后面的路都不考虑了。这是“趋近于结果的”贪心。
2.为什么是到达点的剩余度数呢
我们dijkstra是收集的每个点到起始点( n点 )最短路。 每次操作也是用的当前有的最短路。
本次操作是 n 到达这个点 v 的最短路也是 v 的最优结合我们的思路取最坏封掉其他路要加上剩余度数。
3.相同路是否可以去重用个set
不可以。因为对于最优解可能要让这些路都封掉。
4.如果有多条路相同呢
没关系。等到多条中的最后一条时这条减的度数最小也是这种路的最优解。这几条路不是同一“时空” 参考代码
发现我的dijkstra板子感觉可以简写~~可以看看官方题解的简洁代码
#define endl \n
//#define int long long//不能用set因为那些长的重复的都要删const int maxn 2e5 5;
int arr[maxn];
int d[maxn];
int tmpdis 1;
struct dis_node//放堆里面比长度但是想知道端点
{int dis;int next;bool operator (const dis_node a){return dis a.dis;}dis_node(int 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(vectorint dij, vectorvectorint arr, int ori, int n)
{priority_queuedis_node, vectordis_node, cmpheap;vectorintbarr(arr.size());int cur ori;while (1){barr[cur] 1;for (auto next : arr[cur]){if (dij[next] dij[cur] d[next]){dij[next] dij[cur] d[next];heap.push(dis_node(dij[next], next));}d[next]--;}while (heap.size()){if (barr[heap.top().next] 0)break;heap.pop();}if (heap.size() 0)break;cur heap.top().next;heap.pop();}
}void solve()
{int n, m;cin n m;vectorvectorintarr(n1);vectorintdij(n1,INT_MAX);dij[n] 0;for (int i 0; i m; i){int a, b;cin a b;arr[b].push_back(a);d[a];//a的走法我们是倒着算的其实正着是a - b//我们是用b算的某个a而且可以认为是当前最小a可走}dijkstr(dij, arr, n, 1);cout dij[1] endl;
}
