当前位置:网站首页>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;
}
边栏推荐
- Uniapp pit filling Tour
- How to write the summary? (including 7 easily ignored precautions and a summary of common sentence patterns in 80% of review articles)
- 荐书 |《学者的术与道》:写论文是门手艺
- 【SVN】一直出现 Please execute the ‘Cleanup‘ command,cleanup以后没有反应的解决办法
- 规则引擎Drools的使用
- PHP < => spacecraft operator (combined comparator)
- dijango学习
- 2.9.4 Boolean object type processing and convenient methods of ext JS
- [SVN] please execute the 'cleanup' command appears all the time. The solution is that there is no response after cleanup
- Go Plus Security:一款Build Web3不可或缺的安全生态基础设施
猜你喜欢

【SVN】一直出现 Please execute the ‘Cleanup‘ command,cleanup以后没有反应的解决办法

Apple removed the last Intel chip from its products

Advanced content of MySQL -- three MySQL logs that must be understood binlog, redo log and undo log

Mantium 如何在 Amazon SageMaker 上使用 DeepSpeed 实现低延迟 GPT-J 推理

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

MATLAB绘图

Acwing第 61 场周赛【完结】

VM虚拟机 没有未桥接的主机网络适配器 无法还原默认配置

Luoda Development -- the context of sidetone configuration

How mantium uses deepspeed to implement low latency gpt-j reasoning on Amazon sagemaker
随机推荐
I.MX6U-ALPHA开发板(主频和时钟配置实验)
redux
LeetCode:1184. 公交站间的距离————简单
VM虚拟机 没有未桥接的主机网络适配器 无法还原默认配置
Where does international crude oil open an account, a formal, safe and secure platform
The second article, which is still unfinished, will be introduced again, and continue to explain oracledb_ Exporter monitors Oracle, a very low intrusive monitoring scheme.
Recommendation | scholar's art and Tao: writing papers is a skill
Go plus security: an indispensable security ecological infrastructure for build Web3
Seat / safety configuration upgrade is the administrative experience of the new Volvo S90 in place
(translation) the button position convention can strengthen the user's usage habits
E-commerce operator Xiaobai, how to get started quickly and learn data analysis?
座椅/安全配置升级 新款沃尔沃S90行政体验到位了吗
[SVN] please execute the 'cleanup' command appears all the time. The solution is that there is no response after cleanup
How to transfer English documents to Chinese?
生活相关——一个华科研究生导师的肺腑之言(主要适用于理工科)
MATLAB绘图
Uniapp pit filling Tour
Chapter 18: explore the wonders of the mean in the 2-bit a~b system, specify the 3x+1 conversion process of integers, specify an interval to verify the angular Valley conjecture, explore the number of
Small ball and box model, arrangement and combination
[Reading Notes - > data analysis] Introduction to BDA textbook data analysis