题解 P2984 【[USACO10FEB]给巧克力Chocolate Giving】
交了九九八十一遍，最后终于过了！这道题唯一的难点就是开的数据规模，然后就是一个裸的spfa最短路，下面见我这81次(其实没这么多)交的代码
1. 具体思路就是：让一只奶牛跑到FJ那边，然后再跑回p_i那里。
细心的朋友都发现了，这样太慢！！！而且常量开这么大跑两遍确实非常勉强
于是就爆零了！
1. 具体思路就是：让一只奶牛跑到FJ那边，然后再跑回p_i那里。
细心的朋友都发现了，这样太慢！！！而且常量开这么大跑两遍确实非常勉强
于是就爆零了！
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
const int inf = 0x7fffffff;
const int maxn = 30000001 ;//这里是不是太大了！！
int n,m,t,k,s,e;
int dis[maxn] , vis[maxn] , head[maxn] ;
struct dy{
int x , y , z ,next;
}a[maxn];
void add(int x , int y , int z)//加边
{
a[t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ++ ;
}
void spfa(int s)
{
queue<int>q ;
for(int i = 1 ; i <= n ; i ++) dis[i] = inf ;
memset(vis , false , sizeof(vis)) ;
q.push(s) ;
dis[s] = 0 ;
while(!q.empty())
{
int u = q.front() ;
q.pop() ;
vis[u] = 0 ;
for(int i = head[u] ; i != -1 ; i = a[i].next )
{
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z)
{
dis[v] = dis[u] + a[i].z ;
if(!vis[v])
{
vis[v] = true ;
q.push(v) ;
}
}
}
}
}
int p ;
int main()
{
cin >> n >> m >> p ;
memset(head , -1 , sizeof(head)) ;
while(m --)//建图
{
int x , y , z ;
cin >> x >> y >> z ;
add(x , y , z ) ;
add(y , x , z) ;
}
while( p --)//两遍SPFA
{
cin >> s >> e ;
spfa(s) ;
int w = dis[1] ;//先跑到FJ那里
spfa(1) ;
cout << w + dis[e] <<"\n";//再跑回P_I
}
} 2.发现问题就要解决问题：上面说到常数太大的问题，于是便改吧！略微的超过一点数据范围，但是本蒟蒻有忽视了一个常识性问题：这是一个无向图！数组是要开两倍多一点的！
50分！
2.发现问题就要解决问题：上面说到常数太大的问题，于是便改吧！略微的超过一点数据范围，但是本蒟蒻有忽视了一个常识性问题：这是一个无向图！数组是要开两倍多一点的！
50分！
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
const int inf = 0x7ffffff;
const int maxn = 50010 ;//更改在此处！
int n,m,t,k,s,e;
int dis[maxn] , vis[maxn] , head[maxn] ;//注意这里！应优化为maxn*2+1
struct dy{
int x , y , z ,next;
}a[maxn];
void add(int x , int y , int z)//加边
{
a[t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ++ ;
}
void spfa(int s)
{
queue<int>q ;
for(int i = 1 ; i <= n ; i ++) dis[i] = inf ;
memset(vis , false , sizeof(vis)) ;
q.push(s) ;
dis[s] = 0 ;
while(!q.empty())
{
int u = q.front() ;
q.pop() ;
vis[u] = 0 ;
for(int i = head[u] ; i != -1 ; i = a[i].next )
{
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z)
{
dis[v] = dis[u] + a[i].z ;
if(!vis[v])
{
vis[v] = true ;
q.push(v) ;
}
}
}
}
}
int p ;
int main()
{
cin >> n >> m >> p ;
memset(head , -1 , sizeof(head)) ;
while(m --)
{
int x , y , z ;
cin >> x >> y >> z ;
add(x , y , z ) ;
add(y , x , z) ;
}
while( p --)//打死不改的两遍spfa
{
cin >> s >> e ;
spfa(s) ;
int w = dis[1] ;
spfa(1) ;
cout << w + dis[e] <<"\n";
}
} 3.改进：const 开大了一点，且maxn*2+1了，但是还是RE了一个点(而且吸氧还没用呢！)加上改进了算法：从奶牛到FJ的距离其实就和从FJ到奶牛的距离相等
所以只要求FJ到P_I和Q_I的距离之和就好了！！
3.改进：const 开大了一点，且maxn*2+1了，但是还是RE了一个点(而且吸氧还没用呢！)加上改进了算法：从奶牛到FJ的距离其实就和从FJ到奶牛的距离相等
所以只要求FJ到P_I和Q_I的距离之和就好了！！
90分！
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
const int inf = 0x7ffffff;
const int maxn = 60010 ;
int n,m,t,k,s,e;
int dis[maxn*2+1] , vis[maxn*2+1] , head[maxn*2+1] ;
struct dy{
int x , y , z ,next;
}a[maxn*2+1];
void add(int x , int y , int z)
{
a[t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ++ ;
}
void spfa(int s)
{
queue<int>q ;
for(int i = 1 ; i <= n ; i ++) dis[i] = inf ;
memset(vis , false , sizeof(vis)) ;
q.push(s) ;
dis[s] = 0 ;
while(!q.empty())
{
int u = q.front() ;
q.pop() ;
vis[u] = 0 ;
for(int i = head[u] ; i != -1 ; i = a[i].next )
{
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z)
{
dis[v] = dis[u] + a[i].z ;
if(!vis[v])
{
vis[v] = true ;
q.push(v) ;
}
}
}
}
}
int p ;
int main()
{
cin >> n >> m >> p ;
memset(head , -1 , sizeof(head)) ;
while(m --)
{
int x , y , z ;
cin >> x >> y >> z ;
add(x , y , z ) ;
add(y , x , z) ;
}
spfa(1) ;
while( p --)//改为一遍spfa
{
cin >> s >> e ;
cout <<dis[s] + dis[e] <<"\n";
}
} 4.AC！
这么久了终于过了吗！long long 吗？我感觉和这个没什么大关系；我个人认为是我又把常数扩大了10倍的
4.AC！
这么久了终于过了吗！long long 吗？我感觉和这个没什么大关系；我个人认为是我又把常数扩大了10倍的原因；
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
#define ll long long
const ll inf = 0x7ffffff;
const ll maxn = 1000010 ;//这里扩大了10倍
ll n,m,t,k,s,e;
ll dis[maxn] , vis[maxn] , head[maxn] ;
struct dy{
ll x , y , z ,next;
}a[maxn];
void add(ll x , ll y , ll z)
{
a[t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ++ ;
}
void spfa(ll s)
{
queue<ll>q ;
for(ll i = 1 ; i <= n ; i ++) dis[i] = inf ;
memset(vis , false , sizeof(vis)) ;
q.push(s) ;
dis[s] = 0 ;
while(!q.empty())
{
ll u = q.front() ;
q.pop() ;
vis[u] = 0 ;
for(ll i = head[u] ; i != -1 ; i = a[i].next )
{
ll v = a[i].y ;
if(dis[v] > dis[u] + a[i].z)
{
dis[v] = dis[u] + a[i].z ;
if(!vis[v])
{
vis[v] = true ;
q.push(v) ;
}
}
}
}
}
int p ;
int main()
{
cin >> n >> m >> p ;
memset(head , -1 , sizeof(head)) ;
while(m --)
{
ll x , y , z ;
cin >> x >> y >> z ;
add(x , y , z ) ;
add(y , x , z) ;
}
spfa(1) ;
while( p --)//改为一遍spfa
{
cin >> s >> e ;
cout <<dis[s] + dis[e] <<"\n";
}
} 完结散花！！
京公网安备 11010502036488号