交通规划
emmm感觉怪怪的，大概意思就是无向图中，找出一棵树，满足总权值最小的同时，根节点到所有点最短距离不变。先做一个dijstra，然后对于每个点进行遍历，首先肯定要满足dis[a]不变，在这个前提下减小w[边],那其实可以做一个dp 假设遍历到i点，dp[i-1]+w[边]=dis[i].
我们知道 dp[i]是连接i个节点的最短路径树代价，在dp[i-1]相同的情况下，我们只需要找最短的w[边]然后加入即可
代码如下
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, M = 2e5 + 10;
int n, m;
int head[N], w[M], ne[M], e[M], cnt;
int dis[N];
bool st[N];
void add(int a, int b, int c)
{e[cnt] = b;w[cnt] = c;ne[cnt] = head[a];head[a] = cnt++;
}
void dij()
{priority_queue<PII, vector<PII>, greater<PII>> q;dis[1] = 0;q.emplace(0, 1);while (!q.empty()){auto s = q.top();q.pop();if (st[s.second])continue;st[s.second] = true;for (int i = head[s.second]; ~i; i = ne[i]){int j = e[i];if (!st[j]){dis[j] = dis[j] < dis[s.second] + w[i] ? dis[j] : dis[s.second] + w[i];q.emplace(dis[j], j);}}}
}
void work()
{memset(head, -1, sizeof head);memset(dis, 0x3f, sizeof dis);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}dij();int res = 0;for (int i = 2; i <= n; i++){int minw = inf;for (int j = head[i]; ~j; j = ne[j]){int k = e[j];if (dis[i] == dis[k] + w[j])minw = min(minw, w[j]);}res += minw;}cout << res;return;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);work();return 0;
}行车路线 非常有意思的一道题。主要用了拆点的思想。自身水平不够，理解可能不到位，但其实我感觉是把每个点分为若干个状态，然后 这些状态就都能用相同的dijstra来运算
node里面的比较函数 一定要加const。并且如果要emplace(a,b,c)
必须要添加重载构造函数
node(int a,int b,int c):x(a),y(b),z(c){}代码如下
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 510;
const int M = 2e5 + 10;
int dis[N][1010];
bool st[N][1010];
int head[N], e[M], ne[M], w[M], t[M], cnt;
int n, m;
struct node
{int num, s_road, distance;node(int a, int b, int c) :num(a), s_road(b), distance(c) {}bool operator < (const node& t)const{return distance > t.distance;}
};
priority_queue<node>q;
void add(int a, int b, int c, int d)
{e[cnt] = b;w[cnt] = c;t[cnt] = d;ne[cnt] = head[a];head[a] = cnt++;
}
void dij()
{q.emplace(1, 0, 0);dis[1][0] = 0;while (!q.empty()){auto tmp = q.top();q.pop();if (st[tmp.num][tmp.s_road])continue;st[tmp.num][tmp.s_road] = true;for (int i = head[tmp.num]; ~i; i = ne[i]){int j = e[i];if (t[i] == 1){int y = tmp.s_road, v = tmp.distance;y += w[i];if (y <= 1000) {if (dis[j][y] > v - tmp.s_road * tmp.s_road + y * y){dis[j][y] = v - tmp.s_road * tmp.s_road + y * y;q.emplace(j, y, dis[j][y]);}}}else{if (dis[j][0] > tmp.distance + w[i]){dis[j][0] = tmp.distance + w[i];q.emplace(j, 0, dis[j][0]);}}}}
}
void work()
{memset(head, -1, sizeof head);memset(dis, 0x3f, sizeof dis);cin >> n >> m;while (m--){int a, b, c, d;cin >> d >> a >> b >> c;add(a, b, c, d);add(b, a, c, d);}dij();int ans = 1e6 + 10;for (int i = 0; i < 1001; i++)ans = min(ans, dis[n][i]);cout << ans;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);work();return 0;
}再卖菜 可以参考这个博客了解一下差分约束。感觉就是要找不等式。一个点会满足很多个不等式。如果要找最小值那么就是 Xk>=C0+...，那么其实就是找出最长路径（spfa特殊写法）
如果是找最大值那么就是Xk<=C0+...，那么就是就是求最小路。
平时没有负权边就尽量dij，有的话用spfa。代码如下
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 310, M = 100010;
int head[N], e[M], ne[M], w[M], cnt;
int dis[N];
bool st[N];
int b[N], n;
void add(int a, int b, int c)
{e[cnt] = b;w[cnt] = c;ne[cnt] = head[a];head[a] = cnt++;
}
void spfa()
{memset(dis, -0x3f, sizeof dis);queue<int> q;dis[0] = 0, st[0] = true;q.emplace(0);while (!q.empty()){int t = q.front();q.pop();st[t] = false;for (int i = head[t]; ~i; i = ne[i]){int j = e[i];if (dis[j] < dis[t] + w[i]){dis[j] = dis[t] + w[i];if (!st[j]){q.emplace(j);st[j] = true;}}}}
}
void work()
{memset(head, -1, sizeof head);cin >> n;for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++)add(i - 1, i, 1);for (int i = 2; i < n; i++){add(i - 2, i + 1, 3 * b[i]);add(i + 1, i - 2, -3 * b[i] - 2);}add(0, 2, 2 * b[1]);add(2, 0, -2 * b[1] - 1);add(n - 2, n, 2 * b[n]);add(n, n - 2, -2 * b[n] - 1);spfa();for (int i = 1; i <= n; i++)cout << dis[i] - dis[i - 1] << " ";return;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);work();return 0;
}模板题 差分约束 模板讲的非常好
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5;
int head[N], e[N], ne[N], w[N], cnt;
int n, m;
int dis[N];
int ans[N];
bool st[N];
void add(int a, int b, int c)
{e[cnt] = b;ne[cnt] = head[a];w[cnt] = c;head[a] = cnt++;
}
bool spfa()
{queue<int> q;q.emplace(0);dis[0] = 0;st[0] = true;while (!q.empty()){int x = q.front();q.pop();st[x] = false;for (int i = head[x]; ~i; i = ne[i]){int v = e[i];if (dis[v] > dis[x] + w[i]){dis[v] = dis[x] + w[i];if (!st[v]){st[v] = true;ans[v]++;if (ans[v] == n + 1)return false;q.emplace(v);}}}}return true;
}
void work()
{cin >> n >> m;memset(dis, 0x3f, sizeof dis);memset(head, -1, sizeof head);while (m--){int u, v, w;cin >> u >> v >> w;add(v, u, w);}for (int i = 1; i <= n; i++)add(0, i, 0);if (spfa() == false)cout << "No" << endl;else{for (int i = 1; i <= n; i++)cout << dis[i] << " ";}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);work();return 0;
}
