~~ID伤感~~
by VenusM1nT @ 2018-11-19 15:35:10
spfa没死，不加优化可以过
by nothingness @ 2018-11-19 16:11:55
@[spfa](/space/show?uid=149462)
by Ynoi @ 2018-11-19 17:42:28
有个低级错误，改了一下，还是没过。。。wa
```
#include<cstdio>
#include<cctype>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 1000, MAXM = 100000, INF = 2147483647;
int n, m, cnt1 = 0, cnt2 = 0, ans = 0, d1[MAXN + 10], d2[MAXN + 10], head1[MAXN + 10], head2[MAXN + 10];
bool visit1[MAXN + 10], visit2[MAXN + 10];
struct EDGE{
int next, to, w;
};
EDGE edge1[MAXM + 10], edge2[MAXM + 10];
inline int read(){
char ch = getchar();
int f = 1, x = 0;
while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)){ x = (x << 1) + (x << 3); x += (ch & 15); ch = getchar();}
return f * x;
}
void add1(int f, int t, int v){
edge1[++cnt1].next = head1[f];
edge1[cnt1].to = t;
edge1[cnt1].w = v;
head1[f] = cnt1;
}
void add2(int f, int t, int v){
edge2[++cnt2].next = head2[f];
edge2[cnt2].to = t;
edge2[cnt2].w = v;
head2[f] = cnt2;
}
void spfa1(int x){
fill(d1 + 1, d1 + n + 1, INF);
deque <int> nod1;
nod1.push_back(x); visit1[x] = 1;
while(nod1.size()){
int k = nod1.front(); visit1[k] = 0; nod1.pop_front();
for(int i = head1[k]; i != 0; i = edge1[i].next){
int j = edge1[i].to;
if(d1[j] > d1[k] + edge1[i].w){
d1[j] = d1[k] + edge1[i].w;
if(!visit1[j]){
visit1[j] = 1;
nod1.push_back(j);
}
}
}
}
}
void spfa2(int x){
fill(d2 + 1, d2 + n + 1, INF);
deque <int> nod2;
nod2.push_back(x); visit2[x] = 1;
while(nod2.size()){
int k = nod2.front(); visit2[k] = 0; nod2.pop_front();
for(int i = head2[k]; i != 0; i = edge2[i].next){
int j = edge2[i].to;
if(d2[j] > d2[k] + edge2[i].w){
d2[j] = d2[k] + edge2[i].w;
if(!visit2[j]){
visit2[j] = 1;
nod2.push_back(j);
}
}
}
}
}
int main(){
n = read(); m = read();
while(m--){
int x, y, z;
x = read(); y = read(); z = read();
add1(x, y, z); add2(y, x, z);
}
spfa1(1); spfa2(1);
for(int i = 2; i <= n; i++) ans += (d1[i] + d2[i]);
printf("%d\n", ans);
return 0;
}
```
by Ireliaღ @ 2018-11-20 16:44:43
~~~~
by COVID91 @ 2019-05-04 10:52:36
那么我也来试试SPFA
by Vocalise @ 2019-08-19 14:09:41
```cpp
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int dist[10005];
int vist[10005];
int que[1000005];
int dist2[10005],vist2[10005];
vector<pair<int,int> >g[10005],g2[10005];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(make_pair(v,w));
g2[v].push_back(make_pair(u,w));
}
memset(dist,63,sizeof(dist));
vist[1]=1;
dist[1]=0;
int head=0,tail=0;
que[++tail]=1;
while(head<tail)
{
int pp=que[++head];
vist[pp]=0;
for(int i=0;i<g[pp].size();i++)
{
int cu=g[pp][i].first;
int jl=g[pp][i].second;
if(dist[cu]>dist[pp]+jl)
{
dist[cu]=dist[pp]+jl;
if(!vist[cu])
{
vist[cu]=0;
que[++tail]=cu;
}
}
}
}
memset(dist2,63,sizeof(dist2));
vist2[1]=1;
dist2[1]=0;
head=0,tail=0;
que[++tail]=1;
while(head<tail)
{
int pp=que[++head];
vist[pp]=0;
for(int i=0;i<g2[pp].size();i++)
{
int cu=g2[pp][i].first;
int jl=g2[pp][i].second;
if(dist2[cu]>dist2[pp]+jl)
{
dist2[cu]=dist2[pp]+jl;
if(!vist2[cu])
{
vist2[cu]=0;
que[++tail]=cu;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)ans+=dist[i]+dist2[i];
printf("%d\n",ans);
return 0;
}
```
AC了呀
by wmy_goes_to_thu @ 2019-10-11 16:50:46