Seauy @ 2019-08-18 17:58:27
程序为何未响应啊QAQ 查了半天错都没看出来
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000;
struct DE {int nxt,val;};
int n;
vector<DE> edge[2][MAXN+5];
void Build(int a,int b,int v)
{
edge[0][a].push_back(DE{b,v});
edge[1][b].push_back(DE{a,v});
}
long long SPFA(int start,bool D)
{
//cout<<1<<endl;
bool inQ[MAXN+5];
long long dis[MAXN+5];
queue<int> Q;
memset(inQ,0,sizeof inQ);
for(int i=1;i<=n;i++) dis[i]=(LONG_MAX/2)*(i!=start);
Q.push(start);
while(!Q.empty())
{
int now=Q.front();Q.pop();
inQ[now]=0;
for(int i=0;i<edge[D][now].size();i++)
{
int rear=edge[D][now][i].nxt;
int cost=edge[D][now][i].val;
if(dis[rear]>dis[now]+cost)
{
dis[rear]=dis[now]+cost;
if(!inQ[rear])
{
inQ[rear]=1;
Q.push(rear);
}
}
}
}
long long cnt=0;
for(int i=1;i<=n;i++) cnt+=dis[i];
return cnt;
}
int main()
{
int m;
scanf("%d %d",&n,&m);
while(m--)
{
int a,b,v;
scanf("%d %d %d",&a,&b,&v);
Build(a,b,v);
}
//cout<<1<<endl;
printf("%lld\n",SPFA(1,0)+SPFA(1,1));
return 0;
}
by Seauy @ 2019-08-18 18:04:03
看来是我计算机炸了 QAQ 过都过了,本地还给我停止运行