传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=302
| The Flash |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
"My name is Barry Allen and I'm the fastest man alive. When I was a child, I saw my mom killed by something impossible, and my father went to * for her murder. Then an accident made me the impossible. To the outside world, I'm an ordinary forensic scientist. But secretly, I used my speed to fight crim and find others like me. And one day, I'll find who killed my mother and get justice for my father. I am the flash." 以上是xjr背诵的闪电侠片头的片段。
B.I.T.C.H.们玩得正High时，闪电侠来得瑟他的速度了。他邀请xjr和Avengers观看他夜晚在城市跑步的场景。 他的路线是这样的：（一共有n个城市，城市由1到n编号，城市之间有m条边） 1 → 2 → 1 → 3 → 1 → 4 → 1 → 5 → 1 → … → n-1 → 1 → n → 1 但由于闪电侠速度超过闪电，他也有了一种和电流一样的心理——走最短路，现在你需要回答闪电侠最少需要走多少千米的路程。 |
|
输入
|
|
第一行，两个整数n和m（见试题描述）
接下来m行，每行三个整数a，b和c，表示从a城市到b城市有一条有向边，长度为c |
|
输出
|
|
闪电侠走的最短路程
|
|
输入示例
|
|
5 10
2 3 8 1 5 90 3 5 82 1 2 76 1 3 8 5 3 4 4 1 23 4 5 6 3 5 6 5 4 2 |
|
输出示例
|
|
232
|
|
其他说明
|
|
1 < n, c < 1001
1 < m < 100001 数据保证城市1能到达任何城市，并且任何城市能到达城市1 |
题解：最短路瞎跑大水题（出题人竟然没有卡SPFA！！！）
更新邻接表：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+,inf=1e9;
struct SPFA{
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms;
bool inq[maxn];int d[maxn];
void init(int n){
ms=adj;fill(d,d+n+,inf);memset(inq,false,sizeof(inq));return;
}
void ade(int u,int v,int w){
*ms=(ted){u,v,w,fch[u]};fch[u]=ms++;
return;
}
void spfa(int S){
queue<int>Q;Q.push(S);d[S]=;
while(!Q.empty()){
int u=Q.front();Q.pop();inq[u]=false;
for(ted*e=fch[u];e;e=e->nxt){
int v=e->y;
if(d[v]>d[u]+e->w){
d[v]=d[u]+e->w;
if(!inq[v]) Q.push(v),inq[v]=true;
}
}
} return;
}
}p1,p2;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,m;
void init(){
n=read();m=read();p1.init(n);p2.init(n);
int x,y,w;
for(int i=;i<=m;i++){
x=read();y=read();w=read();
p1.ade(x,y,w);p2.ade(y,x,w);
}
p1.spfa();p2.spfa();
int ans=;
for(int i=;i<=n;i++){
ans+=p1.d[i]+p2.d[i];
} write(ans);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
数组版：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define inf 10000000
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+;
struct ShortiestPath{
struct Tedge{int x,y,w,next;}adj[maxm];int fch[maxn],ms;
int d[maxn],S,n;bool inque[maxn];
void AddEdge(int u,int v,int w){adj[++ms]=(Tedge){u,v,w,fch[u]};fch[u]=ms;return;}
void init(int S,int n){
this->S=S;this->n=n;ms=;
memset(inque,false,sizeof(inque));
memset(fch,,sizeof(fch));
for(int i=;i<=n;i++) d[i]=inf;
return;
}
void SPFA(){
queue<int>Q;d[S]=;Q.push(S);
while(!Q.empty()){
int u=Q.front();Q.pop();inque[u]=false;
for(int i=fch[u];i;i=adj[i].next){
int v=adj[i].y;
if(d[v]>d[u]+adj[i].w){
d[v]=d[u]+adj[i].w;
if(!inque[v]){
inque[v]=true;
Q.push(v);
}
}
}
} return;
}
}p1,p2;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,m;
void init(){
n=read();m=read();
p1.init(,n);p2.init(,n);
for(int i=;i<=m;i++){
int a=read(),b=read(),c=read();
p1.AddEdge(a,b,c);
p2.AddEdge(b,a,c);
}
return;
}
void work(){
p1.SPFA();p2.SPFA();
return;
}
void print(){
int ans=;
for(int i=;i<=n;i++){
ans+=p1.d[i]+p2.d[i];
}
write(ans);
return;
}
int main(){init();work();print();return ;}
当然啦还是写Dijkstra比较稳妥，小健建のDijkstra：（原谅我懒到一定境界了。。。）
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
const int INF=;
struct Edge
{
int from,to,dist;
};
struct Heapnode
{
int d,u;
bool operator < (const Heapnode& rhs) const
{
return d>rhs.d;
}
};
struct Dijkstra
{
int n,m;
int p[maxn];
Edge edges[maxm];
int first[maxn],next[maxm];
int d[maxn];
bool done[maxn];
void init(int n)
{
this->n=n;
m=;
memset(first,,sizeof(first));
}
void AddEdge(int from,int to,int dist)
{
edges[++m]=(Edge){from,to,dist};
next[m]=first[from];
first[from]=m;
}
void dijkstra(int s)
{
memset(done,,sizeof(done));
priority_queue<Heapnode> Q;
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
Q.push((Heapnode){,s});
while(!Q.empty())
{
Heapnode x=Q.top();
Q.pop();
if(done[x.u]) continue;
done[x.u]=;
for(int i=first[x.u];i;i=next[i])
{
Edge& v=edges[i];
if(d[v.to]>d[x.u]+v.dist)
{
d[v.to]=d[x.u]+v.dist;
Q.push((Heapnode){d[v.to],v.to});
}
}
}
}
}sol1,sol2;
int main()
{
int n,m,a,b,c;
scanf("%d%d",&n,&m);
sol1.init(n); sol2.init(n);
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
sol1.AddEdge(a,b,c);
sol2.AddEdge(b,a,c);
}
sol1.dijkstra(); sol2.dijkstra();
long long ans=;
for(int i=;i<=n;i++) ans+=sol1.d[i]+sol2.d[i];
printf("%lld\n",ans);
return ;
}