dijkstra 板子题求条

问题讨论区 提高段
1 
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define vv first
#define ww second
using namespace std;
int n,m;
int dis[100005];
bool vis[100005];
vector<PII>a[100005];
priority_queue<PII,vector<PII>,greater<PII> >q;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(u==v) continue;
		a[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++) dis[i]=LLONG_MAX;
	q.push({0,1});
	while(!q.empty()){
		int v=q.top().vv,w=q.top().ww;
		q.pop();
		if(vis[v]) continue;
		vis[v]=1,dis[v]=w;
		for(int i=0;i<a[v].size();i++){
			PII now=a[v][i];
			if(vis[now.vv]) continue;
			q.push({now.vv,w+now.ww});
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==LLONG_MAX) cout<<"inf ";
		else cout<<dis[i]<<" ";
	}
	return 0;
}
2

数组开到200005

3

不是，因为开到500005都没用

4

[quote=“string dp[100005], post:1, topic:34929, full:true, username:张乐凡”]

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define vv first
#define ww second
using namespace std;
int n,m;
int dis[100005];
bool vis[100005];
vector<PII>a[100005];
priority_queue<PII,vector<PII>,greater<PII> >q;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(u==v) continue;
		a[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++) dis[i]=LLONG_MAX;
	q.push({1,0});
	for(int i=1;i<=n;i++){
		int v=q.top().vv,w=q.top().ww;
		q.pop();
		if(vis[v]) continue;
		vis[v]=1,dis[v]=w;
		for(int i=0;i<a[v].size();i++){
			PII now=a[v][i];
			if(vis[now.vv]) continue;
			q.push({now.vv,w+now.ww});
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==LLONG_MAX) cout<<"inf ";
		else cout<<dis[i]<<" ";
	}
	return 0;
}

[/quote]

主函数外部分：

struct box{
	long long v_i,w_i;
};
struct box2{
	long long distance,ii;
	//按dixtance从大到小 
};
long long n,m;
vector<box> a[200005];
long long ans[200005];
priority_queue<box2> q;//按距离从大到小的优先队列 
void f(long long stt){
	ans[stt]=0;
	q.push({0,stt});
	while(!q.empty()){
		box2 tmp=q.top();
		q.pop();
		long long pt=tmp.ii;
		if(tmp.distance>ans[pt]){
			continue;
		}
		for(auto i:a[pt]){
			//自己写 
		}
	}
}
1 个赞
5

主函数外部分给你了，给方案+赞

6

@杨思越 你是怎么看到他们的题目的？

7

因为是板子题，大家都能看，洛谷上可以搜到