休眠了2月了 要振作起来了！！。。。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2155
因为点比较少 最多更新三百次 标记某个节点时直接更新与之相连的点的最短距离
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 using namespace std; 8 #define INF 0xfffffff 9 int w[310][310],f[310]; 10 int main() 11 { 12 int n,m,i,j,q; 13 int kk = 1; 14 while(cin>>n>>m>>q) 15 { 16 if(n==0&&m==0&&q==0) break; 17 int u,v,c; 18 memset(f,0,sizeof(f)); 19 for(i = 0 ; i < n ; i++) 20 { 21 for(j = 0 ;j < n ; j++) 22 w[i][j] = INF; 23 w[i][i] = 0; 24 } 25 for(i = 1; i <= m ; i++) 26 { 27 cin>>u>>v>>c; 28 w[u][v] = min(w[u][v],c); 29 } 30 printf("Case %d: ",kk++); 31 while(q--) 32 { 33 int t; 34 cin>>t; 35 if(t==1) 36 { 37 int x,y; 38 cin>>x>>y; 39 if(!f[x]||!f[y]) 40 printf("City %d or %d is not available. ",x,y); 41 else if(w[x][y]==INF) 42 puts("No such path."); 43 else 44 printf("%d ",w[x][y]); 45 } 46 else 47 { 48 int x; 49 cin>>x; 50 if(f[x]) 51 { 52 printf("City %d is already recaptured. ",x); 53 continue; 54 } 55 f[x] = 1; 56 for(i = 0 ; i < n ; i++) 57 for(j = 0 ; j < n ; j++) 58 if(w[i][j]>w[i][x]+w[x][j]) 59 w[i][j] = w[i][x]+w[x][j]; 60 } 61 } 62 puts(""); 63 } 64 return 0; 65 } 66 67 68 69 70 /************************************** 71 Problem id : SDUT OJ 2155 72 User name : shang 73 Result : Accepted 74 Take Memory : 832K 75 Take Time : 300MS 76 Submit Time : 2014-01-16 15:11:20 77 **************************************/
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2159
set存结构体 low_bounder二分查找 不过时间跑了不少 不知道有没有更简单的方法
1 #include<cstdio> 2 #include<cstring> 3 #include <cmath> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<iostream> 10 using namespace std; 11 struct node 12 { 13 int x,y; 14 bool operator <(const node a) const 15 { 16 if(a.x==x) 17 return y<a.y; 18 return x<a.x; 19 } 20 }; 21 char s[10]; 22 int main() 23 { 24 int n,kk=1; 25 while(cin>>n) 26 { 27 if(!n) break; 28 set<node>q; 29 node st; 30 printf("Case %d: ", kk++); 31 while(n--) 32 { 33 cin>>s; 34 if(s[0]=='a') 35 { 36 cin>>st.x>>st.y; 37 q.insert(st); 38 } 39 else if(s[0]=='f') 40 { 41 cin>>st.x>>st.y; 42 set<node>::iterator it; 43 it = q.lower_bound(st); 44 while(it!=q.end()) 45 { 46 if((*it).x>st.x&&(*it).y>st.y) 47 { 48 cout<<(*it).x<<" "<<(*it).y<<endl; 49 break; 50 } 51 it++; 52 } 53 if(it==q.end()) 54 puts("-1"); 55 } 56 else 57 { 58 cin>>st.x>>st.y; 59 q.erase(st); 60 } 61 } 62 puts(""); 63 } 64 return 0; 65 } 66 67 68 69 70 /************************************** 71 Problem id : SDUT OJ 2159 72 User name : shang 73 Result : Accepted 74 Take Memory : 2572K 75 Take Time : 930MS 76 Submit Time : 2014-01-16 17:34:20 77 **************************************/
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2157
先取两个数 再二分查找和与m最近的数
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 using namespace std; 8 int a[1010],p[1010*1010]; 9 int main() 10 { 11 int n,m,i,j; 12 int kk = 1; 13 while(scanf("%d%d",&n,&m)!=EOF) 14 { 15 if(!n&&!m) break; 16 for(i = 0; i < n ; i++) 17 scanf("%d",&a[i]); 18 a[n] = 0; 19 int g = 0; 20 for(i = 0 ; i <= n; i++) 21 for(j = i ; j <= n ; j++) 22 if(a[i]+a[j]<=m) 23 p[g++] = a[i]+a[j]; 24 sort(p,p+g); 25 int maxz = 0; 26 printf("Case %d: ",kk++); 27 for(i = 0 ; i < g ; i++) 28 { 29 if(p[i]>m) break; 30 int low = i,high = g-1; 31 while(low<high) 32 { 33 int mm = (low+high)/2; 34 if(p[i]+p[mm]>m) 35 high = mm-1; 36 else 37 low = mm+1; 38 } 39 if(p[low]+p[i]<=m&&p[low]+p[i]>maxz) 40 { 41 maxz = p[low]+p[i]; 42 } 43 } 44 printf("%d ",maxz); 45 puts(""); 46 } 47 return 0; 48 } 49 50 51 52 53 /************************************** 54 Problem id : SDUT OJ 2157 55 User name : shang 56 Result : Accepted 57 Take Memory : 2444K 58 Take Time : 130MS 59 Submit Time : 2014-01-16 15:43:45 60 **************************************/