当前位置:网站首页>Dijikstra (preprocessing first) +dfs, relocation truncated to fit
Dijikstra (preprocessing first) +dfs, relocation truncated to fit
2022-07-26 04:14:00 【Selvaggia】
Global variables ( Array ) It's big
I was going to have a dist【N】[N]
/tmp/cccMPc7i.o: In function `dijikstra(int)':
a.cpp:(.text+0xb3): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0xe3): relocation truncated to fit: R_X86_64_32S against symbol `vis' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x154): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x1a2): relocation truncated to fit: R_X86_64_32S against symbol `vis' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x1ba): relocation truncated to fit: R_X86_64_32S against symbol `vis' defined in .bss section in /tmp/cccMPc7i.o
/tmp/cccMPc7i.o: In function `dfs(int, int, int)':
a.cpp:(.text+0x378): relocation truncated to fit: R_X86_64_32S against symbol `st' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x38a): relocation truncated to fit: R_X86_64_32S against symbol `st' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x3f6): relocation truncated to fit: R_X86_64_32S against symbol `st' defined in .bss section in /tmp/cccMPc7i.o
/tmp/cccMPc7i.o: In function `main':
a.cpp:(.text+0x419): relocation truncated to fit: R_X86_64_32 against symbol `n' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x428): relocation truncated to fit: R_X86_64_32 against symbol `m' defined in .bss section in /tmp/cccMPc7i.o
a.cpp:(.text+0x46f): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f
#define pii pair<int,int>
const int N=5e4+10;
const int M=1e5+5;
int id[10];
struct edge{
int to,nxt,w;
}e[M<<1];
int head[N];
int cnt;
void add(int u,int v,int w){
e[++cnt].w=w;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int dist[10][N];
bool vis[N];
int n,m;
void dijikstra(int s){
for(int i=1;i<=n;i++){
dist[s][i]=inf;
vis[i]=false;
}
priority_queue<pii, vector<pii> ,greater<pii> > Q;
Q.push({
0,s});
dist[s][s]=0;
for(int k=0;k<n;k++){
if(Q.empty())break;
pii t=Q.top(); Q.pop();
int v=t.second;
if(vis[v]){
k--;
continue;
}
vis[v]=1;
for(int i=head[v];i;i=e[i].nxt){
int to=e[i].to;
int w=e[i].w;
if(dist[s][to]>dist[s][v]+w){
dist[s][to]=dist[s][v]+w;
Q.push({
dist[s][to],to});
}
}
}
}
bool st[10];
int dfs(int p,int station,int dis){
if(station==5)return dis;
int res=inf;
for(int i=1;i<=5;i++){
if(!st[i]){
st[i]=true;
res=min(res,dfs(id[i],station+1,dis+dist[p][id[i]]));
st[i]=false;
}
}
return res;
}
int main(int argc, char** argv) {
cin>>n>>m;
id[0]=1;// Jiajia family
for(int i=1;i<=5;i++)cin>>id[i];
int u,v,w;
while(m--){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<=5;i++)dijikstra(id[i]);
cout<<dfs(1,0,0); // Where is it at this time , How many stations have you reached , How much time has it taken
return 0;
}
In this example Segmentation Fault
11 15
11 4 9 10 8
1 3 7
1 5 5
1 4 10
1 2 6
9 5 3
5 6 8
6 3 7
3 2 2
2 8 5
8 4 8
3 8 8
2 7 11
6 10 20
10 7 12
4 11 30
Turned out to be dist[][] Save site to site , The station number can be more than 10
Can only save The number of the must visit site (0~5) It is reasonable and does not exceed the memory
#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f
#define pii pair<int,int>
const int N=5e4+10;
const int M=1e5+5;
int id[10];
struct edge{
int to,nxt,w;
}e[M<<1];
int head[N];
int cnt;
void add(int u,int v,int w){
e[++cnt].w=w;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int dist[10][N];
bool vis[N];
int n,m;
void dijikstra(int s,int sg){
for(int i=1;i<=n;i++){
dist[sg][i]=inf;
vis[i]=false;
}
priority_queue<pii, vector<pii> ,greater<pii> > Q;
Q.push({
0,s});
dist[sg][s]=0;
for(int k=0;k<n;k++){
if(Q.empty())break;
pii t=Q.top(); Q.pop();
int v=t.second;
if(vis[v]){
k--;
continue;
}
vis[v]=1;
for(int i=head[v];i;i=e[i].nxt){
int to=e[i].to;
int w=e[i].w;
if(dist[sg][to]>dist[sg][v]+w){
dist[sg][to]=dist[sg][v]+w;
Q.push({
dist[sg][to],to});
}
}
}
}
bool st[10];
int dfs(int p,int station,int dis){
if(station==5)return dis;
int res=inf;
for(int i=1;i<=5;i++){
if(!st[i]){
st[i]=true;
res=min(res,dfs(i,station+1,dis+dist[p][id[i]]));
st[i]=false;
}
}
return res;
}
int main(int argc, char** argv) {
cin>>n>>m;
id[0]=1;// Jiajia family
for(int i=1;i<=5;i++)cin>>id[i];
int u,v,w;
while(m--){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<=5;i++)dijikstra(id[i],i);
cout<<dfs(0,0,0); // At this time in 6 Individual station (0~5) The number of , How many stations have you reached , How much time has it taken
return 0;
}
边栏推荐
- (translation) the button position convention can strengthen the user's usage habits
- Dracoo master
- 荐书丨《教育心理学》:送给明日教师的一本书~
- How to write the abbreviation of the thesis?
- E-commerce operator Xiaobai, how to get started quickly and learn data analysis?
- 2.9.4 Ext JS的布尔对象类型处理及便捷方法
- Advanced content of MySQL -- three MySQL logs that must be understood binlog, redo log and undo log
- 华为高层谈 35 岁危机,程序员如何破年龄之忧?
- Connect external MySQL databases in istio Service Grid
- Implementation of distributed lock
猜你喜欢

Lua and go mixed call debugging records support cross platform (implemented through C and luajit)

Wechat applet to realize music player (4) (use pubsubjs to realize inter page communication)

工程师如何对待开源 --- 一个老工程师的肺腑之言

Opencv learning notes - edge detection and Canny operator, Sobel operator, lapiacian operator, ScHARR filter

吴恩达机器学习课后习题——线性回归

支持代理直连Oracle数据库,JumpServer堡垒机v2.24.0发布

This article takes you to graph transformers

Sentinel fusing and current limiting

综合评价与决策方法

5 years, 1.4W times, NFT og's road to immortality Web3 column
随机推荐
规则引擎Drools的使用
Functions of anonymous functions
Yadi started to slow down after high-end
Worked overtime for a week to develop a reporting system. This low code free it reporting artifact is very easy to use
Inventory the concept, classification and characteristics of cloud computing
华为再发“天才少年”全球召集令,有人曾放弃360万年薪加入
What format should be adopted when the references are foreign documents?
When you try to delete all bad code in the program | daily anecdotes
综合评价与决策方法
Overview of wavelet packet transform methods
Retail chain store cashier system source code management commodity classification function logic sharing
makefile知识再整理(超详细)
Opencv learning notes -- Hough transform
Wechat applet realizes music player (5)
解决:RuntimeError: Expected object of scalar type Int but got scalar type Double
Soft simulation rasterization renderer
MATLAB绘图
Seat / safety configuration upgrade is the administrative experience of the new Volvo S90 in place
Web Test Method Encyclopedia
Sorting and searching