PRabbitdad @ 2023-08-01 22:06:00
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXT = 2e5 + 5;
const int MAXM = 3e5 + 5;
const int MOD = 998244353;
using namespace std;
int dis[MAXN];
int n,m,s;
vector<pair<int,int> >G[MAXN];
void dijkstra(){
for(int i=0;i<MAXN;i++) dis[i] = INT_MAX;
priority_queue<int,vector<int>,greater<int> >q;
dis[s] = 0;
q.push(s);
while(q.size()){
int now = q.top();
q.pop();
for(int i=0;i<G[now].size();i++){
int u = G[now][i].first;
int d = G[now][i].second;
if(dis[u] > dis[now] + d){
dis[u] = dis[now] + d;
q.push(u);
}
}
}
return;
}
signed main(){
cin >> n >> m >> s;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
dijkstra();
for(int i=1;i<=n;i++){
cout << dis[i] << " ";
}
return 0;
}
by FL_sleake @ 2023-08-01 22:24:18
写个pair或者node
by wzb13958817049 @ 2023-08-01 22:24:20
@GRATRABBIT 啊啊啊啊啊！？哪道
by PRabbitdad @ 2023-08-01 22:24:43
哦，谢懂了%%%
by FL_sleake @ 2023-08-01 22:24:59
塞进去的u是点序号，不是dis
by PRabbitdad @ 2023-08-01 22:25:15
@wzb13958817049 Fox and Jumping
by PRabbitdad @ 2023-08-01 22:25:31
#include<bits/stdc++.h>
using namespace std;
int n;
int l[305];
int c[305];
map<int,long long>dis;
priority_queue<int,vector<int>,greater<int> >q;
void dijkstra(){
dis[0] = 0;
q.push(0);
while(q.size()){
int now = q.top();
q.pop();
for(int i=1;i<=n;i++){
int y = __gcd(now,l[i]);
if(!dis[y]) dis[y] = INT_MAX;
if(dis[y] > dis[now] + c[i]){
dis[y] = dis[now] + c[i];
q.push(y);
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&l[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
dijkstra();
if(!dis[1]){
puts("-1");
return 0;
}
printf("%d",dis[1]);
return 0;
}by PRabbitdad @ 2023-08-01 22:25:52
我怕是对Dij有什么误解。
by FL_sleake @ 2023-08-01 22:26:11
%%%
其实以前看Atcoder题解一直没懂，现在才知道priority_queue<int,vector<int>,greater<int> >q;就是按升序排序了
Orz
by wzb13958817049 @ 2023-08-01 22:27:09
@GRATRABBIT 等等他不是单向图吗！你怎么入度两次
by PRabbitdad @ 2023-08-01 22:27:59
那我可以duque?如果大的话尾插，否则头插？