阴语飞 @ 2022-02-18 09:31:05
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxn=1e5 +7;
int dis[maxn];
int vis[maxn];
long long ans=0;
struct node
{
int v,len;
};
vector<node> e[maxn];
void dijkstra1(int x)
{
memset(dis,63,sizeof dis);
priority_queue<pair<int ,int > > q;
q.push(make_pair(0,x));
dis[x]=0;
//vis[x]=1;
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i].v;
if(dis[v]>dis[u]+e[u][i].len)
{
dis[v]=dis[u]+e[u][i].len;
q.push(make_pair(-dis[v],v));
}
}
}
}
void dijkstra2(int x)//x=n
{
memset(dis,63,sizeof dis);
priority_queue<pair<int ,int > > q;
q.push(make_pair(0,x));
dis[x]=0;
memset(vis,0,sizeof vis);
vis[x]=1;
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
//vis[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i].v;
if(dis[v]>dis[u]+e[u][i].len)
{
dis[v]=dis[u]+e[u][i].len;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].push_back({b,c});//结构体加大括号
}
dijkstra1(1);
for(int i=1;i<=n;i++)
{
ans=ans+dis[i];
}
dijkstra2(n);
for(int i=1;i<=n;i++)
{
ans=ans+dis[i];
}
printf("%d",&ans);
}
by Arctic_1010 @ 2022-02-18 09:49:58
@阴语飞
请检查您代码最后一行的输出语句，并回忆是否混用 scanf 的用法。
by Arctic_1010 @ 2022-02-18 09:53:07
@阴语飞 或者直接说
printf("%d",&ans);
^您输出的是 ans 变量的地址，所以值会很奇怪。
by 阴语飞 @ 2022-02-18 10:12:25
@0Arctic0 谢谢谢谢，已经AC了，不加“&”，还得开longlong，改成lld，前面还有许多错误QWQ
by 阴语飞 @ 2022-02-18 10:12:56
#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
const int maxn=1e6 +7;
long long dis[maxn];
int vis[maxn];
long long ans=0;
struct node
{
int v,len;
};
vector<node> e[maxn];
vector<node> e2[maxn];
void dijkstra1(int x)
{
memset(dis,127,sizeof dis);//long long 赋值127
priority_queue<pair<long long,int > > q;
q.push(make_pair(0,x));
dis[x]=0;
//vis[x]=1;
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i].v;
if(dis[v]>dis[u]+e[u][i].len)
{
dis[v]=dis[u]+e[u][i].len;
q.push(make_pair(-dis[v],v));//取堆中最小的数放入堆
}
}
}
}
void dijkstra2(int x)//x=n
{
memset(dis,127,sizeof dis);
priority_queue<pair<long long,int> > q; //定义大根堆中一个元素有2个数
q.push(make_pair(0,x));//把pair的数据放入
dis[x]=0;
memset(vis,0,sizeof vis);
//vis[x]=1;
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<e2[u].size();i++)
{
int v=e2[u][i].v;
if(dis[v]>dis[u]+e2[u][i].len)
{
dis[v]=dis[u]+e2[u][i].len;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(long long i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].push_back({b,c});//结构体加大括号
e2[b].push_back({a,c});
}
dijkstra1(1);
for(int i=1;i<=n;i++)
{
ans=ans+dis[i];
}
//cout<<ans<<'\n';
dijkstra2(1);
for(int i=1;i<=n;i++)
{//cout<<dis[i]<<" ";
ans=ans+dis[i];
}
printf("%lld",ans);
}