休眠了2月了 要振作起来了！！。。。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2155
因为点比较少 最多更新三百次 标记某个节点时直接更新与之相连的点的最短距离
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define INF 0xfffffff
int w[][],f[];
int main()
{
int n,m,i,j,q;
int kk = ;
while(cin>>n>>m>>q)
{
if(n==&&m==&&q==) break;
int u,v,c;
memset(f,,sizeof(f));
for(i = ; i < n ; i++)
{
for(j = ;j < n ; j++)
w[i][j] = INF;
w[i][i] = ;
}
for(i = ; i <= m ; i++)
{
cin>>u>>v>>c;
w[u][v] = min(w[u][v],c);
}
printf("Case %d:\n",kk++);
while(q--)
{
int t;
cin>>t;
if(t==)
{
int x,y;
cin>>x>>y;
if(!f[x]||!f[y])
printf("City %d or %d is not available.\n",x,y);
else if(w[x][y]==INF)
puts("No such path.");
else
printf("%d\n",w[x][y]);
}
else
{
int x;
cin>>x;
if(f[x])
{
printf("City %d is already recaptured.\n",x);
continue;
}
f[x] = ;
for(i = ; i < n ; i++)
for(j = ; j < n ; j++)
if(w[i][j]>w[i][x]+w[x][j])
w[i][j] = w[i][x]+w[x][j];
}
}
puts("");
}
return ;
} /**************************************
Problem id : SDUT OJ 2155
User name : shang
Result : Accepted
Take Memory : 832K
Take Time : 300MS
Submit Time : 2014-01-16 15:11:20
**************************************/
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2159
set存结构体 low_bounder二分查找 不过时间跑了不少 不知道有没有更简单的方法
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
using namespace std;
struct node
{
int x,y;
bool operator <(const node a) const
{
if(a.x==x)
return y<a.y;
return x<a.x;
}
};
char s[];
int main()
{
int n,kk=;
while(cin>>n)
{
if(!n) break;
set<node>q;
node st;
printf("Case %d:\n", kk++);
while(n--)
{
cin>>s;
if(s[]=='a')
{
cin>>st.x>>st.y;
q.insert(st);
}
else if(s[]=='f')
{
cin>>st.x>>st.y;
set<node>::iterator it;
it = q.lower_bound(st);
while(it!=q.end())
{
if((*it).x>st.x&&(*it).y>st.y)
{
cout<<(*it).x<<" "<<(*it).y<<endl;
break;
}
it++;
}
if(it==q.end())
puts("-1");
}
else
{
cin>>st.x>>st.y;
q.erase(st);
}
}
puts("");
}
return ;
} /**************************************
Problem id : SDUT OJ 2159
User name : shang
Result : Accepted
Take Memory : 2572K
Take Time : 930MS
Submit Time : 2014-01-16 17:34:20
**************************************/
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2157
先取两个数 再二分查找和与m最近的数
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
int a[],p[*];
int main()
{
int n,m,i,j;
int kk = ;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m) break;
for(i = ; i < n ; i++)
scanf("%d",&a[i]);
a[n] = ;
int g = ;
for(i = ; i <= n; i++)
for(j = i ; j <= n ; j++)
if(a[i]+a[j]<=m)
p[g++] = a[i]+a[j];
sort(p,p+g);
int maxz = ;
printf("Case %d: ",kk++);
for(i = ; i < g ; i++)
{
if(p[i]>m) break;
int low = i,high = g-;
while(low<high)
{
int mm = (low+high)/;
if(p[i]+p[mm]>m)
high = mm-;
else
low = mm+;
}
if(p[low]+p[i]<=m&&p[low]+p[i]>maxz)
{
maxz = p[low]+p[i];
}
}
printf("%d\n",maxz);
puts("");
}
return ;
} /**************************************
Problem id : SDUT OJ 2157
User name : shang
Result : Accepted
Take Memory : 2444K
Take Time : 130MS
Submit Time : 2014-01-16 15:43:45
**************************************/