题解 SP50 【INCARDS - Invitation Cards】
Farkas_W
·
·
题解
\text{题目大意}
$\quad$虽然$SPFA$已经死了，但还是值得一用的，对于这道题考虑使用$SPFA$求最短路。
$\quad$根据题意，我们可以开二维数组,第一层存正图，第二层存反图，然后跑两边$SPFA$，将每个点的距离累加到$ans$上，然后输出$ans$即可。
**一些需要注意点**
1. 多组数据，每次记得清空数组。
2. 尽量不要使用例如$next$等变量名，会CE。~~全机房貌似就我不知道~~
3. 票价总和不超过1000000000，可以使用$int$。
4. 数据读入输出会非常大，建议使用快读快输,不用可能会$T$飞。
如果不会就看看代码吧
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define il inline
#define inf 0x3f3f3f3f
#define next nne
#define re register int
using namespace std;
il int read() //快读
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
il void print(int x) //快输
{
if(x<0)putchar('-'),x=-x;
if(x/10)print(x/10);
putchar(x%10+'0');
}
const int N=1e6+5;
int n,m,k,dis[N],ans=0;
int next[N][2],s[N][2],go[N][2],head[N][2],tot;
bool b[N];
il void Add(int x,int y,int z) //链式前向星存图
{
next[++tot][1]=head[x][1];
head[x][1]=tot;
go[tot][1]=y;
s[tot][1]=z;
next[tot][0]=head[y][0];
head[y][0]=tot;
go[tot][0]=x;
s[tot][0]=z;
}
il void SPFA(int p) //模板SPFA
{
deque<int>q; //双调队列
for(re i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
q.push_front(1);
b[1]=1;
while(!q.empty())
{
int x=q.front();
q.pop_front();
b[x]=0;
for(re i=head[x][p];i;i=next[i][p])
{
int y=go[i][p];
if(dis[y]>dis[x]+s[i][p])
{
dis[y]=dis[x]+s[i][p];
if(!b[y]){
b[y]=1;
if(q.empty())q.push_back(y);//双调队列优化
else if(dis[y]<dis[q.front()])q.push_front(y);
else q.push_back(y);
}
}
}
}
}
signed main()
{
int t=read();
while(t--)
{
tot=ans=0;
memset(s,0,sizeof(s));
memset(dis,0,sizeof(dis));
memset(head,0,sizeof(head));
n=read();m=read();
for(re i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
Add(x,y,z);
}
SPFA(1);
for(re i=1;i<=n;i++)ans+=dis[i];
SPFA(0);
for(re i=1;i<=n;i++)ans+=dis[i];
print(ans);putchar('\n');
}
return 0;
}
```
$$\text{后话}$$
此题有多倍经验哦
[UVA721 Invitation Cards](https://www.luogu.com.cn/problem/UVA721)
[P1342 请柬](https://www.luogu.com.cn/problem/P1342)
[P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)
[P1821 [USACO07FEB] Cow Party S](https://www.luogu.com.cn/problem/P1821)