冈崎梦美 @ 2018-07-07 23:02:09
样例能过,一交就错
#include<bits/stdc++.h>
#define debug printf("Viva La France\n");
using namespace std;
const int maxn=1000001;
struct edge
{
int to,dist;
};
vector<edge> G[maxn];
vector<edge> G1[maxn];
int n,m;
long long ans;
int read()
{
int x=0;char ch;
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
void spfa(int s)
{
bool vis[maxn];fill(vis+1,vis+n+1,false);
int dis[maxn];fill(dis+1,dis+n+1,0x7f);
deque<int>team;team.push_front(s);
vis[s]=true;dis[s]=0;
while(!team.empty())
{
//debug
int q=team.front();team.pop_front();vis[q]=false;
for(int i=0;i<G[q].size();i++)
{
edge e=G[q][i];
if (dis[e.to]>dis[q]+e.dist)
{
dis[e.to]=dis[q]+e.dist;
if (!vis[e.to])
{
if ((team.empty())||(dis[e.to]<=dis[team.front()])) team.push_front(e.to);
else team.push_back(e.to);
vis[e.to]=true;
}
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
}
void spfa1(int s)
{
bool vis[maxn];memset(vis,false,sizeof(vis));
int dis[maxn];memset(dis,0x7f,sizeof(dis));
deque<int>team;team.push_front(s);
vis[s]=true;dis[s]=0;
while(!team.empty())
{
//debug
int q=team.front();team.pop_front();vis[q]=false;
for(int i=0;i<G1[q].size();i++)
{
edge e=G1[q][i];
if (dis[e.to]>dis[q]+e.dist)
{
dis[e.to]=dis[q]+e.dist;
if (!vis[e.to])
{
if ((team.empty())||(dis[e.to]<=dis[team.front()])) team.push_front(e.to);
else team.push_back(e.to);
vis[e.to]=true;
}
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
G[u].push_back((edge){v,w});
G1[v].push_back((edge){u,w});
}
spfa(1);
spfa1(1);
write(ans);
return 0;
}
by 冈崎梦美 @ 2018-07-08 14:15:33
最值赋小了,并且要开LL,此贴已坟,勿回。
by 冈崎梦美 @ 2018-07-08 16:47:36
还有,不需要SLF,LLL之类的优化,裸SPFA能过