做了一题，开心，冒一下泡：
题目大意：有一些草原（1，……，p个），告诉你n个奶牛的在哪个草原，Famer John 会在其中一个草原放一块糖，
让所有的奶牛去舔（提高奶的质量^-^），要求的就是把糖放在哪个草原使所有的奶牛到那的路程和最短。
（当然奶牛都是拣最短的路走）。
第一种超时思路 ：Floyd算法求出任意两个草原间的距离，枚举所有草原，取所有奶牛所在的草原到该草原和的最大值。
很不幸TLE了，O（800^3）；
第二种超时思路：用Dijkstra+priority_queue(优先级队列)，枚举所有草原算单源最短路径，如果不优化还是O(800^3)
用priority_queue还是TLE了，Dijkstra找最近的的时候用优先级队列很快，O（1），调整O（log n），可能是用的不够好。
貌似有人用这种方法做出来。不知道用邻接表行不行。
第三种思路：就是SPFA算法（Shortest Path Fast Algorithm）：
用邻接表，枚举所有草原，用SPFA算单源最短路径，SPFA算法要用到队列，一个标记数组用于判断是否在队列中,
d[]数组，存放i到所有点的距离，初始值都为MAX，d[i]=0。
枚举的草原i先入队。如果队列非空就开始迭代，取队首元素x并弹出它，对于所有与x相邻的（邻接表的好处体现了）u，
如果d[u]>d[x]+len(x,u)(x到u的距离)d[u]=d[x]+len(x,u)，这样d[u]进行更新了，d[u]可能会继续更新别的点，
如果u不在队列的话，就把u放在队列中。一直迭代下去，直到队列为空（就是说没有在更新了）;
1# TLE
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 5544 KB]
Test 2: TEST OK [0.000 secs, 5544 KB]
Test 3: TEST OK [0.011 secs, 5544 KB]
Test 4: TEST OK [0.022 secs, 5544 KB]
Test 5: TEST OK [0.022 secs, 5544 KB]
Test 6: TEST OK [0.054 secs, 5544 KB]
Test 7: TEST OK [0.410 secs, 5544 KB]
> Run 8: Execution error: Your program (`butter') used more than the
allotted runtime of 1 seconds (it ended or was stopped at 1.339
seconds) when presented with test case 8. It used 5544 KB of
memory.
|
想用Foloyd（）求最短路径，超时了。
/*
ID:tbbd4261
PROG:butter
LANG:C++
*/
#include<fstream>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
int adj[MAX][MAX]={0};
int location[505];
int n,p,c;
ifstream fin("butter.in");
ofstream fout("butter.out");
void init()
{
int i,j;
for(i=1; i<=p; i++)
for(j=1; j<=p; j++)
adj[i][j]=INF;
for(i=1; i<=p; i++)
adj[i][i]=0;
}
void Floyd()
{
int i,j,k;
for(k=1; k<=p; k++)
for(i=1; i<=p; i++)
for(j=1; j<=p; j++)
{
if(i==j)continue;
if(adj[i][j]>adj[i][k]+adj[k][j])
adj[i][j]=adj[i][k]+adj[k][j];
}
}
void print()
{
int i,j;
for(i=1; i<=p; i++,fout<<endl)
for(j=1; j<=p; j++)
fout<<adj[i][j]<<' ';
}
int main()
{
fin>>n>>p>>c;
init();
for(int i=1; i<=n; i++ )
fin>>location[i];
for(int i=1,len,s,t; i<=c; i++)
{
fin>>s>>t>>len;
adj[t][s]=adj[s][t]=len;
}
Floyd();
int minSum=INF,sum;
for(int i=1; i<=p; i++)
{
bool f=true;
sum=0;
for(int j=1; j<=n; j++)
{
if(adj[i][location[j]]!=INF)
{
sum+=adj[i][location[j]];
}
else f=false;
}
if(f==true&&sum<minSum)minSum=sum;
}
fout<<minSum<<endl;
return 0;
}
2，TLE
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 5552 KB]
Test 2: TEST OK [0.022 secs, 5552 KB]
Test 3: TEST OK [0.011 secs, 5552 KB]
Test 4: TEST OK [0.011 secs, 5552 KB]
Test 5: TEST OK [0.032 secs, 5552 KB]
Test 6: TEST OK [0.097 secs, 5552 KB]
Test 7: TEST OK [0.637 secs, 5552 KB]
> Run 8: Execution error: Your program (`butter') used more than the
allotted runtime of 1 seconds (it ended or was stopped at 1.674
seconds) when presented with test case 8. It used 5552 KB of
memory.
|
改用Dijkstra+priority_queue(STL)更慢了…………
/*
ID:tbbd4261
PROG:butter
LANG:C++
*/
#include<fstream>
#include<iostream>
#include<queue>
#include<functional>
#include<cstring>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
int n,p,c;
int location[505]={0};
int adj[MAX][MAX]={0};
ifstream fin("butter.in");
ofstream fout("butter.out");
typedef pair<int ,int > type;
int d[MAX];
bool done[MAX];
int dijkstra(int t)
{
memset(done,0,sizeof done);
for(int i=1; i<=p; i++)
d[i]=INF;
d[t]=0;
priority_queue<int ,vector<type > ,greater<type> >q;
q.push(make_pair(d[t],t));
type temp;
while(!q.empty())
{
temp=q.top(); q.pop();
int x=temp.second;
if(done[x])continue;
done[x]=true;
//fout<<x<<' '<<d[x]<<endl;
for(int j=1; j<=p; j++)
{
if(d[j]>d[x]+adj[x][j])
{
d[j]=d[x]+adj[x][j];
q.push(make_pair(d[j],j));
}
}
}
int ans=0;
for(int i=1; i<=n; i++)
if(d[location[i]]==INF)return -1;
else ans+=d[location[i]];
return ans;
}
void init()
{
int i,j;
for(i=1; i<=p; i++)
for(j=1; j<=p; j++)
adj[i][j]=(i==j?0:INF);
}
void print()
{
fout<<"print location: "<<endl;
for(int i=1; i<=n; i++)
fout<<location[i]<<' ';
fout<<endl;
fout<<"print adj: "<<endl;
for(int i=1; i<=p; i++,fout<<endl)
for(int j=1; j<=p; j++)
fout<<adj[i][j]<<' ';
fout<<endl;
}
int main()
{
fin>>n>>p>>c;
init();
for(int i=1; i<=n; i++)
fin>>location[i];
for(int i=1,s,t,len; i<=c; i++)
{
fin>>s>>t>>len;
adj[s][t]=adj[t][s]=len;
}
//print();
int min=INF;
for(int i=1,tt; i<=p; i++)
{
tt= dijkstra(i);
//system("pause");
if(tt!=-1&&tt<min)
min=tt;
}
fout<<min<<endl;
//system("pause");
return 0;
}
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 8084 KB]
Test 2: TEST OK [0.000 secs, 8084 KB]
Test 3: TEST OK [0.011 secs, 8084 KB]
Test 4: TEST OK [0.022 secs, 8084 KB]
Test 5: TEST OK [0.000 secs, 8084 KB]
Test 6: TEST OK [0.011 secs, 8084 KB]
Test 7: TEST OK [0.054 secs, 8084 KB]
Test 8: TEST OK [0.108 secs, 8084 KB]
Test 9: TEST OK [0.162 secs, 8084 KB]
Test 10: TEST OK [0.173 secs, 8084 KB]
All tests OK.
Your program ('butter') produced all correct answers! This is your
submission #5 for this problem. Congratulations!
3,A了！
千呼万唤始出来，终于A了，而且速度挺快！！！
传说中的SPFA算法：
/*
ID:tbbd4261
PROG:butter
LANG:C++
*/
#include<fstream>
#include<cstring>
#include<queue>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
ifstream fin("butter.in");
ofstream fout("butter.out");
struct node{
int end,len;
};
int cnt[MAX]={0},location[505]={0},n,p,c;
node adj[MAX][MAX];
bool in[MAX]={0};
int d[MAX];
int SPFA(int i)
{
memset(in,0,sizeof in);
for(int k=1; k<=p; k++)d[k]=INF;
queue<int> Q;
Q.push(i);
in[i]=true;
d[i]=0;
while(!Q.empty())
{
int x=Q.front(); Q.pop();
in[x]=false;
for(int j=0; j<cnt[x]; j++)
if(d[x]+adj[x][j].len < d[ adj[x][j].end ])
{
d[adj[x][j].end]=d[x]+adj[x][j].len;
if(!in[adj[x][j].end])
{
Q.push(adj[x][j].end);
in[adj[x][j].end ]=true;
}
}
}
int ans=0;
for(int j=1; j<=n; j++)
{
if(d[location[j]]==INF)return -1;
else ans+=d[location[j]];
}
return ans;
}
void print()
{
int i,j;
for(i=1; i<=p ; i++)
for(j=0; j<cnt[i]; j++)
{
fout<<i<<' '<<adj[i][j].end<<' '<<adj[i][j].len<<endl;
}
}
int main()
{
memset(cnt,0,sizeof cnt);
fin>>n>>p>>c;
for(int i=1; i<=n; i++)
fin>>location[i];
for(int i=1,s,t,value; i<=c; i++)
{
fin>>s>>t>>value;
adj[s][cnt[s]].end=t; adj[s][cnt[s]].len=value; cnt[s]++;
adj[t][cnt[t]].end=s; adj[t][cnt[t]].len=value; cnt[t]++;
}
int tt,min=INF;
for(int i=1; i<=p; i++)
{
tt=SPFA(i);
if(tt<min&&tt!=-1) min=tt;
}
fout<<min<<endl;
//system("pause");
return 0;
}