dij专题
【建模】【dij】【枚举所有可能区间】
昂贵的聘礼 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 41108 Accepted: 11977 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求
【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】
Silver Cow Party Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15522 Accepted: 7039 Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going
poj 1062 dij
如题：http://poj.org/problem?id=1062 这一题不难发现，就是一个最短路径的问题，题目已经规定最终要换到的物品是第一个，然后给出另外几个可以优惠的节点，比如这个图，0-1的最小代价是0-4-3-1 也就是5250。 如何建图？0是源点，map【0】【i】代表第i个物
HDU 3035 War 平面最小割+优先队列优化的dij
题意：给一个矩形图（具体看图），左上角的点为起点，右下角的点为终点。图中每一条边都有权值，所以要是想切断一些边，使得起点终点不能相通，问需要切掉边的最小权值。 想法：网络流最小割当然可以做，但是点有501*501+500*500，很尴尬太多了。所以可以从左下角，向右上角切割来阻断路径（平面最小割）。这个要把每一个被线分割的区域当做一个点，每个区域之间的线的权值为边的权值。这个里面有一个类似
POJ - 1502 MPI Maelstrom dij模板题
题目链接 POJ-1502 题意 有n个基站，给定m条线路，线路上有不同的时间，从1号基站开始发送信息，当每一个基站接到信息时，它同时向其他基站发送信息，问多久能传输给所有基站。 解法 裸的最短路，画出图手推一下就知道任意基站得到信息的时间就是最短路跑出来的dis数组的值。跑一遍最短路算法找到dis数组最大值输出即可。注意输入，x代表inf，需要拿字符串处理一下，不能无脑cin。 代码
PAT 1003. Emergency (25) dij+增加点权数组和最短路径个数数组
1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue As an emergency rescue team leader of a city, you are given a special map of your c
宁波工程学院2020新生校赛（重现赛）（A,B,C,D,E 二进制优化多重背包 ,F 模拟,G bfs,H 模拟, I 双向dij 方案数 J, K 思维 L 并查集）
战绩： A-恭喜小梁成为了宝可梦训练家~ 签到题 #pragma GCC optimize(2)#include<bits/stdc++.h>#define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#de
最小费用最大流dij板子
不说了，宏定义害死人 #include<bits/stdc++.h>#define Pair pair<long long, long long>#define fi first#define se second/*宏定义害死人*///#define AddEdge(x,y,f,z) add_edge(x,y,f,z);add_edge(y,x,0,-z);// #define ge
武理校赛D题 星际穿越（分层图 + dij堆优化）
武理校赛D题 星际穿越（分层图 + dij堆优化） 牛客链接 题意： 给定 N 个点，M 条边，每条边有边权 w，点分为三类，编号为1，2，3。 给定起点和终点且保证起点和终点都是第 3 类点。 求起点到终点的最短路，且路径中需要有一个 （不多不少刚好一个）1 类点和一个 2 类点，通过 1 类点的时间要在通过 2 类点之前。 保证数据无重边，无负环，图连通。 思路： 第一眼看过
本周图论的flod和dij算法
第一题 输入 #1 8 91 21 31 42 52 63 74 74 87 8 输出 #1 1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8 解读： 中规中矩的图论题，记得这个题需要排序，写一个dfs和bfs就好，要用到vis数组，还有这题可以直接用vector来存储节点信息，（vector是首要选择的数据结构），我们也可以为了插入节点方便
P1266 速度限制 （ dij分层 + 图上dp
#include<bits/stdc++.h>using namespace std;using VI = vector<int>;using ll = long long;using PII = pair <int , int>;const int mod = 998244353;int n,m,d;int idx = 0 ;struct edge{int to,from;int
poj-3114-Countries in War-tarjan缩点建图+dij求最短路
tarjan缩点建图，用了一上午的时间写好了模版。 但是在求最短路的时候不小心使用了floyd，乃至超时。 这不科学。。按照正常的时间复杂度，应该超时不了的。 下午比赛，晚上把之修改为dij，最后通过了~~ #include<stdio.h>#include<string.h>#include<algorithm>#include<stack>#include<vector>