ZJ的偶像包袱

本文主要是介绍ZJ的偶像包袱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用dfs会错，不明白为什么。

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#include<cmath>
using namespace std;
#define ll long long
const unsigned ll INF= 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 7;
ll dis[maxn];
ll vis[maxn];
struct edge {ll u,w;bool operator < (edge a) const{return w>a.w;}
}C[maxn];
priority_queue<edge>q;
vector<ll>v[maxn];
vector<ll>w[maxn];
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(dis,INF,sizeof(dis));int n, m, s, t;cin >> n >> m >> s >> t;for (int i = 0; i < m; i++) {ll a, b, c;cin >> a >> b >> c;v[a].push_back(b);w[a].push_back(c);C[a].w = c;}C[s].u = s;C[s].w = 1;q.push(C[s]);dis[s] = 1;while (!q.empty()) {edge d = q.top();q.pop();ll u = d.u;vis[u] = 1;for (int i = 0; i < v[u].size(); i++){if (vis[v[u][i]])continue;else if (dis[u] * w[u][i]<dis[v[u][i]]){dis[v[u][i]] = dis[u] * w[u][i];d.u = v[u][i];d.w = dis[v[u][i]];q.push(d);}}}if (dis[t] == INF)cout << "impossible" << endl;else cout << dis[t] << endl;return 0;
}

AC代码，dijkstra不断优先队列，不断更新踩实数据。

这篇关于ZJ的偶像包袱的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---