题意:给你一些交通方式和站点,不同的交通方式碳排放不一样,问从起点到终点距离不超过B的路径中最少的碳排放是多少。
思路:二维dijkstra,建图什么的倒不是很难,主要就是对二维dij的理解了;
表示的到达 点 距离 的最小二氧化碳花费
具体见代码(具体的dp思想还没想好)。
int sx, sy, ex, ey;
int mx;
int n, m, cnt;
int cot[N];
bool st[M][M];
PII p[N];
vector<array<int, 3>> g[N];
int dis[M][110]; // dis[i][j]为到了第i个点距离为j 时的最低碳排放量,就相当于dp的状态表示
int get(PII a, PII b)
{int x = a.xx - b.xx;int y = a.yy - b.yy;int t = ceil(sqrt(x * x + y * y));return t;
}
struct node
{int a, b, c;
} edge[N];
struct NODE
{int mon, dis, u;bool operator<(const NODE &w) const // 先距离再co2{if (dis != w.dis)return dis > w.dis;return mon > w.mon;}
};
void dijkstra()
{priority_queue<NODE> q;for (int i = 0; i < M; i++)for (int j = 0; j <= mx; j++)dis[i][j] = 1e18;dis[m][0] = 0;q.push({0, 0, m});while (q.size()){auto [M, D, u] = q.top();q.pop();if (st[u][D])// 由于距离的限制,并不是确定过最短路后就标记不再跑了,// 而是可以有多个距离经过这个点(不一定是最短路),// 然后这个点的这个点的co2被多种到这点的方式更新// 确定为这个距离下的最小co2花费,//(可能当前这一步的距离大了一点但是较其他距离的二氧化碳花费更少,// 所以我们要跟新所有合理距离,每一个距离取一个最小二氧化碳花费)// 才标记不再松弛优化距离这样才可以确保整体co2的最优值continue;st[u][D] = 1;for (auto [v, w1, w2] : g[u]){if (D + w2 > mx)continue;if (dis[v][D + w2] > dis[u][D] + w1){dis[v][D + w2] = dis[u][D] + w1;q.push({dis[v][D + w2], D + w2, v});}}}
}
void solve()
{cin >> sx >> sy >> ex >> ey;cin >> mx >> cot[0];cin >> n;for (int i = 1; i <= n; i++)cin >> cot[i];cin >> m;for (int i = 0; i < m; i++){cin >> p[i].xx >> p[i].yy;int x;cin >> x;for (int j = 1; j <= x; j++){int v, c;cin >> v >> c;edge[++cnt] = {i, v, c};}}for (int i = 1; i <= cnt; i++){auto [u, v, c] = edge[i];int dist = get(p[u], p[v]);g[u].pb({v, dist * cot[c], dist});g[v].pb({u, dist * cot[c], dist});}p[m] = {sx, sy};p[m + 1] = {ex, ey};for (int i = 0; i < m; i++){int dist1 = get(p[m], p[i]);int dist2 = get(p[m + 1], p[i]);g[m].pb({i, dist1 * cot[0], dist1});g[i].pb({m, dist1 * cot[0], dist1});g[m + 1].pb({i, dist2 * cot[0], dist2});g[i].pb({m + 1, dist2 * cot[0], dist2});}int dist = get(p[m], p[m + 1]);g[m + 1].pb({m, dist * cot[0], dist});g[m].pb({m + 1, dist * cot[0], dist});dijkstra();int ans = 1e18;for (int i = 0; i <= mx; i++)ans = min(ans, dis[m + 1][i]);if (ans == 1e18)cout << -1 << endl;elsecout << ans << endl;
}