做了一題，開心，冒一下泡：
題目大意：有一些草原（1，……，p個），告訴你n個奶牛的在哪個草原，F(xiàn)amer John 會在其中一個草原放一塊糖，
讓所有的奶牛去舔（提高奶的質(zhì)量^-^），要求的就是把糖放在哪個草原使所有的奶牛到那的路程和最短。
（當(dāng)然奶牛都是揀最短的路走）。
第一種超時思路 ：Floyd算法求出任意兩個草原間的距離，枚舉所有草原，取所有奶牛所在的草原到該草原和的最大值。
很不幸TLE了，O（800^3）；
第二種超時思路：用Dijkstra+priority_queue(優(yōu)先級隊列)，枚舉所有草原算單源最短路徑，如果不優(yōu)化還是O(800^3)
用priority_queue還是TLE了，Dijkstra找最近的的時候用優(yōu)先級隊列很快，O（1），調(diào)整O（log n），可能是用的不夠好。
貌似有人用這種方法做出來。不知道用鄰接表行不行。
第三種思路：就是SPFA算法（Shortest Path Fast Algorithm）：
用鄰接表，枚舉所有草原，用SPFA算單源最短路徑，SPFA算法要用到隊列，一個標(biāo)記數(shù)組用于判斷是否在隊列中,
d[]數(shù)組，存放i到所有點(diǎn)的距離，初始值都為MAX，d[i]=0。
枚舉的草原i先入隊。如果隊列非空就開始迭代，取隊首元素x并彈出它，對于所有與x相鄰的（鄰接表的好處體現(xiàn)了）u，
如果d[u]>d[x]+len(x,u)(x到u的距離)d[u]=d[x]+len(x,u)，這樣d[u]進(jìn)行更新了，d[u]可能會繼續(xù)更新別的點(diǎn)，
如果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;
}