挑战程序系列

首页 > 代码库 > 挑战程序系列

2024-09-10 07:54:17 215人阅读

1.6二分法

 1 题目：有n张纸片，随机取4张（可放回），如4张面值加起来可等于m，则输出yes，否则no。纸片的面值为k[1],k[2]……
 2 
 3        思路：使用4次循环寻找会导致超时，所以假设4张分别为a,b,c,d，
 4 
 5 先计算二次循环a+b所有可能放入数组kk，然后将kk排序，
 6 
 7 最后使用二次循环（m-c-d）与kk用二分法比较，，最后确定是否有这个值。
 8 
 9 #include <stdio.h>
10 #include <algorithm>
11 using namespace std;
12 bool ss(int x);
13 void solve();
14     int n,m,r,k[500];
15     int kk[500];
16     bool f;
17 int main()
18 {
19     while(scanf("%d %d",&n,&m)!=EOF)
20     {
21         for(int i=0;i<n;i++)
22             scanf("%d",&k[i]);
23         solve();
24         if(f) printf("Yes\n");
25         else printf("NO\n");
26     }
27     return 0;
28 }
29 
30 void solve()
31 {
32     for(int a=0;a<n;a++)
33         for(int b=0;b<n;b++)
34         kk[a*n+b]=k[a]+k[b];
35          sort(kk,kk+n*n);
36           f=false;
37     for(int c=0;c<n;c++)
38         for(int d=0;d<n;d++)
39         if(ss(m-k[c]-k[d]))
40        {
41          f=true;
42        }
43 }
44 
45 bool ss(int x)
46 {
47     int l=0;r=n*n;
48     while(r-l>=1)
49     {
50         int i=(r+l)/2;
51         if(kk[i]>x)l=i+1;
52         else if (kk[i]==x) return true;
53         else r=i;
54     }
55 }
56 
57 
58 Tip:此题也可以使用检索a然后排序，然后（m-b-c-d）与a用二分法比较，套路差不多，但是第一种方法的思想明显比较高大上。
59 
60 对了，局部变量可以与全局变量重名，但是局部变量会屏蔽全局变量哦！！

1.6

2.1穷竭搜索

DFS

 1 /*
 2 input：
 3 7 7
 4 ..#.#..
 5 ..#.#..
 6 ###.###
 7 ...@...
 8 ###.###
 9 ..#.#..
10 ..#.#..         表示有13个可以走到的地方（包括原来那一格）。*/
11 
12 
13 #include <stdio.h>
14 char ch[24][24];
15 void solve(int H,int W);
16 void find1(int H,int W);
17 void dfs(int x,int y,int H,int W);
18 int main()
19 {
20     int H,W,i;
21     while(scanf("%d%d",&W,&H)!=EOF&&H!=0&&W!=0)
22     {
23         getchar();
24      for(i=0;i<H;i++)
25         gets(ch[i]);
26      find1(H,W);
27      solve(H,W);
28     }
29     return 0;
30 }
31 
32 void solve(int H,int W)
33 {
34     int a=0;
35     for(int i=0;i<H;i++)
36         for(int k=0;k<W;k++)
37             if(ch[i][k]==‘@‘)
38                 a++;
39      printf("%d\n",a);
40 }
41 
42 void find1(int H,int W)
43 {
44     for(int i=0;i<H;i++)
45         for(int k=0;k<W;k++)
46             if(ch[i][k]==‘@‘)
47                 {
48                     dfs(i,k,H,W);
49                     return;
50                 }
51 }
52 
53 void dfs(int x,int y,int H,int W)
54 {
55     int x1,y1,nx,ny;
56     ch[x][y]=‘@‘;
57     for(x1=-1;x1<=1;x1++)
58     {
59         nx=x+x1;
60             if(nx>=0&&nx<H&&ch[nx][y]!=‘#‘&&ch[nx][y]!=‘@‘)
61                 dfs(nx,y,H,W);
62     }
63     for(y1=-1;y1<=1;y1++)
64     {
65         ny=y+y1;
66             if(ny>=0&&ny<W&&ch[x][ny]!=‘#‘&&ch[x][ny]!=‘@‘)
67                 dfs(x,ny,H,W);
68     }
69     return;
70 }
71 
72 POJ2386

POJ2386

 1 #include <stdio.h>
 2 char ch[24][24];
 3 void solve(int H,int W);
 4 void find1(int H,int W);
 5 void dfs(int x,int y,int H,int W);
 6 int main()
 7 {
 8     int H,W,i;
 9     while(scanf("%d%d",&W,&H)!=EOF&&H!=0&&W!=0)
10     {
11         getchar();
12      for(i=0;i<H;i++)
13         gets(ch[i]);
14      find1(H,W);
15      solve(H,W);
16     }
17     return 0;
18 }
19 
20 void solve(int H,int W)//计数
21 {
22     int a=0;
23     for(int i=0;i<H;i++)
24         for(int k=0;k<W;k++)
25             if(ch[i][k]==‘@‘)
26                 a++;
27      printf("%d\n",a);
28 }
29 
30 void find1(int H,int W)//找到点
31 {
32     for(int i=0;i<H;i++)
33         for(int k=0;k<W;k++)
34             if(ch[i][k]==‘@‘)
35                 {
36                     dfs(i,k,H,W);
37                     return;
38                 }
39 }
40 
41 void dfs(int x,int y,int H,int W)
42 {
43     int x1,y1,nx,ny;
44     ch[x][y]=‘@‘;
45     for(x1=-1;x1<=1;x1++)
46     {
47         nx=x+x1;
48             if(nx>=0&&nx<H&&ch[nx][y]!=‘#‘&&ch[nx][y]!=‘@‘)
49                 dfs(nx,y,H,W);
50     }
51     for(y1=-1;y1<=1;y1++)
52     {
53         ny=y+y1;
54             if(ny>=0&&ny<W&&ch[x][ny]!=‘#‘&&ch[x][ny]!=‘@‘)
55                 dfs(x,ny,H,W);
56     }
57     return;
58 }
59 
60 POJ1979

POJ1979

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 char ch[102][102];
 5 int xx[4]={0,1,0,-1};
 6 int yy[4]={1,0,-1,0};
 7 int H,W,cou;
 8 void DFS(int x, int y){
 9     int a=0;
10     char b=ch[x][y];
11     ch[x][y]=‘.‘;
12     for(int i = 0; i < 4; i++)
13     {
14         int xn = x + xx[i], yn = y + yy[i];
15         if(xn >= 0 && xn < W && yn >= 0 && yn < H && ch[xn][yn] == b)
16         {
17             DFS(xn, yn);
18         }
19     }
20     return ;
21 }
22 
23 int main()
24 {
25     while(cin >> W >> H && (H && W))
26     {
27         cou = 0;
28         for(int i=0; i < W; i++)
29             for(int k=0; k < H; k++)
30             cin >> ch[i][k];
31         for(int i = 0; i < W; i++)
32                 for(int k = 0; k < H; k++)
33                     if(ch[i][k] != ‘.‘)
34                     {
35                         DFS(i, k);
36                         cou++;
37                     }
38         cout << cou << endl;
39     }
40     return 0;
41 }
42 
43 AOJ0033

AOJ0033 CN

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 int dx[4]={ 0, 1, -1, 0};
 6 int dy[4]={ 1, 0, 0, -1};
 7 int map1[22][22];
 8 int xn,yn,x1,y1,H,W,y2,x2,a;
 9 void dfs(int x1, int y1, int step){
10     if(step > 10) return ;
11     for(int i = 0; i < 4; i++){//四个方向
12         int xn = x1 + dx[i], yn = y1 + dy[i];
13         if(xn == x2 && yn == y2){
14             a=min(a, step + 1);
15             continue;
16         }
17         if(map1[xn][yn] == 1)continue;
18         while(xn >= 0 && xn < W && yn >= 0 && yn < H){
19                 xn += dx[i]; yn += dy[i];//继续往下面走
20             if(xn >= 0 && xn < W && yn >= 0 && yn < H)
21             {
22                 if(map1[xn][yn] == 0) continue;//直到撞墙或终点
23                 if(xn == x2 && yn == y2){//到达终点
24                     a= min(a, step + 1);
25                     return ;
26                 }
27                 map1[xn][yn] = 0;//停下来了，继续dfs，注意dfs前后面的墙。
28                 dfs(xn - dx[i], yn - dy[i], step + 1);
29                 map1[xn][yn] = 1;
30                 break;
31             }
32         }
33     }
34 return ;
35 }
36 
37 int main()
38 {
39     while(cin >> H >> W && H != 0 && W != 0){
40      for(int i = 0; i < W; i++)
41         for(int k = 0; k < H; k++){
42             cin >> map1[i][k];
43             if(map1[i][k] == 2){
44                 x1 = i; y1 = k;
45                 map1[i][k] = 0;
46             }
47             if(map1[i][k] == 3){
48                 x2 = i;
49                 y2 = k;
50                 map1[i][k] = 1;
51             }
52         }
53         a = 99;
54         dfs(x1, y1, 0);
55         if(a == 99 || a>10) cout << "-1" << endl;
56         else cout << a <<endl;
57     }
58     return 0;
59 }

POJ3009

BFS

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 int map1[305][305],step[305][305];
 6 typedef pair<int, int> P;
 7 struct stu{
 8 int x; int y; int t;
 9 };
10 struct stu ch[50002];
11 
12 int dx[5]={0, 1, 0, -1, 0};
13 int dy[5]={0, 0, 1, 0, -1};
14 
15 void zha(int M) {
16     memset(map1, -1, sizeof(map1));
17     for(int i = 0; i < M; i++)
18         for(int k = 0; k < 5; k++){//five points are burst.
19             int nx = ch[i].x + dx[k];
20             int ny = ch[i].y + dy[k];
21             if(nx >= 0 && nx < 303 && ny >= 0 && ny < 303 && (ch[i].t < map1[ny][nx] || map1[ny][nx] == -1))
22                 map1[ny][nx] = ch[i].t;//give everypoint the minimum burst time.
23         }
24 }
25 
26 int bfs() {
27 queue <P> que;
28 que.push( P (0, 0));
29 memset(step, -1, sizeof(step));
30 step[0][0]=0;
31 while(que.size()) {
32     P p= que.front();
33     que.pop();
34         if(map1[p.first][p.second] == -1){//find map1‘s -1 and print it
35             return step[p.first][p.second];
36         }
37     if(step[p.first][p.second] >= map1[p.first][p.second])continue;//the point had benn burst,so jump it
38     for(int i = 1; i < 5; i++) {//this is the point of four diretions that does not been destroy.
39         int nx = p.first + dx[i],ny = p.second + dy[i];
40         if(nx>=0 && ny >=0 &&step[nx][ny] == -1)//if it can arrive and does not exceed the map
41             {
42                  que.push(P(nx, ny));//push it to the queue and go
43                  step[nx][ny]=step[p.first][p.second]+1;//of course,step must add 1 when go.
44             }
45     }
46 }
47 return -1;
48 }
49 
50 int main()
51 {
52     int M,a;
53     while(~scanf("%d",&M))
54     {
55          for(int i=0; i<M; i++)
56             scanf("%d%d%d",&ch[i].x,&ch[i].y,&ch[i].t);
57          zha(M);
58          a=bfs();
59          printf("%d\n",a);
60     }
61     return 0;
62 }

POJ3669

 1 #include <iostream>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 typedef pair<int, int> P;
 6 int sx,sy,H,W,N;
 7 char map1[1002][1002];
 8 int step[1002][1002];
 9 int dx[4] = {1,0,-1,0};
10 int dy[4] = {0,1,0,-1};
11 void find1(int g){
12 for(int i = 0; i < W; i++)
13     for(int k = 0; k < H; k++)
14         if(map1[i][k] == ‘S‘ || map1[i][k] == (g+48)){
15         if(map1[i][k] == ‘S‘) map1[i][k] =‘.‘;
16         sx = i; sy = k;
17         return ;
18     }
19 }
20 
21 int bfs(int n)
22 {
23     memset(step,-1,sizeof(step));
24     queue <P> que;
25     que.push(P (sx,sy));
26     step[sx][sy] = 0;
27     while(que.size()){
28         int x = que.front().first, y = que.front().second;
29         que.pop();
30         for(int i = 0; i < 4; i++){
31             int xn = x + dx[i], yn = y + dy[i];
32             if(xn >= 0 && xn < W && yn >= 0 && yn < H && map1[xn][yn] != ‘X‘ && step[xn][yn] == -1)
33                 {
34                     step[xn][yn] = step[x][y] + 1;
35                     if(map1[xn][yn] == (n+48))
36                         {
37                             return step[xn][yn];
38                         }
39                     que.push(P(xn, yn));
40                 }
41         }
42     }
43 return 0;
44 }
45 
46 int main()
47 {
48     cin >> W >> H >> N;
49     for(int i = 0; i < W; i++)
50         for(int k = 0; k < H; k++)
51         cin >> map1[i][k];
52     int step = 0;
53     find1(0);
54     step += bfs(1);
55     for(int i = 1; i < N; i++)
56     {
57 
58         find1(i);
59         step += bfs(i+1);
60     }
61     cout << step << endl;
62     return 0;
63 }

AOJ0558 CN

 1 #include <iostream>
 2 #include <queue>
 3 #include <string.h>
 4 #include <map>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int d[4]={ 1, -1, 4, -4};
 9 map<string, int> dp;
10 
11 void bfs(){
12 queue<string> que;
13 que.push("01234567");
14 dp["01234567"] = 0;
15 while(que.size()){
16     string now =que.front();
17     que.pop();
18     int p=0;
19     for(int j = 0; j < 8; j++)
20         if(now[j] == ‘0‘){
21             p=j;
22             break;
23         }
24     for(int i = 0; i < 4; i++){
25         int pn= p + d[i];
26         if(pn >= 0 && pn < 8 && !(p == 3 && i == 0)
27          && !(p ==4 && i == 1)){
28             string next = now;
29             swap(next[p],next[pn]);
30             if(dp.find(next) == dp.end()){
31                 dp[next] = dp[now] + 1;
32                 que.push(next);
33                 }
34             }
35         }
36     }
37 return ;
38 }
39 
40 int main()
41 {
42     string line;
43     bfs();
44     while(getline(cin,line))
45     {
46      line.erase(remove(line.begin(), line.end(), ‘ ‘), line.end());
47      cout << dp[line] << endl;
48     }
49     return 0;
50 }

AOJ0121 CN

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 int N,ch[12],sh[12],g,i,cou;
 7 bool judge[12];
 8 
 9 void solve(int a){
10     int leng=0,b=0;
11     for(int k = 0;k < i; k++)
12         if(!judge[k]){//如果没被访问过，就加入数组sh和b
13             sh[leng++] = ch[k];
14             b=b * 10 + ch[k];
15         }
16     if(sh[0] != 0 || leng == 1)
17         cou = min(cou,abs(a-b));
18     while(next_permutation(sh,sh+leng)){//（除了原数组）全排列的所有情况
19         b=0;
20         for(int k = 0; k < leng; k++)
21             b = b * 10 + sh[k];
22         if(sh[0] != 0 || leng == 1)
23             {
24                 cou = min(cou,abs(a-b));
25             }
26     }
27 return ;
28 }
29 
30 void dfs(int x, int y){
31     if(x == i/2){
32         solve(y);
33         return;
34     }
35     for(int k=0; k < i; k++){
36         if(!judge[k]){
37             if(ch[k] == 0 && x == 0 && i > 3)
38                 continue;
39             judge[k]=true;//被访问过
40             dfs(x + 1, y * 10 + ch[k]);
41             judge[k]=false;
42         }
43     }
44     return ;
45 }
46 
47 
48 int main()
49 {
50     cin >> N;
51     getchar();
52     while(N--){
53         for( i = 0;;){
54                 cin>> ch[i++];
55                 if(g=getchar() == ‘\n‘)
56                     break;
57             }
58         cou=1000000;
59         memset(judge,false,sizeof(judge));
60         dfs(0,0);
61         cout << cou <<endl;
62     }
63     return 0;
64 }

POJ2718

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int n,sum;
 5 int tri[10][10];
 6 
 7 int main()
 8 {
 9     while(cin >> n >> sum)
10     {
11         int lie[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
12         do{
13                 for(int k = 0; k < n; k++)
14                     tri[0][k]=lie[k];//first line
15                 for(int i = 1; i < n; i++)
16                     for(int g = 0 ; g < n - i; g++)//next line
17                     tri[i][g] = tri[i-1][g] + tri[i-1][g+1];
18                 if(tri[n-1][0] == sum )
19                     break;
20         } while(next_permutation(lie, lie+n));
21 
22         for(int j = 0; j < n ; j++){
23             if(j != 0)
24                 cout << " ";
25             cout << lie[j];
26         }
27         cout << endl;
28     }
29     return 0;
30 }

POJ3187

 1 #include <iostream>
 2 using namespace std;
 3 int map1[5][5],cou[10000000];
 4 int a,n,h;
 5 int x1[4] = {0, 1, -1, 0};
 6 int y1[4] = {1, 0, 0, -1};
 7 
 8 void dfs(int x, int y, int c, int all){
 9 if(c == 6)
10     {
11         cou[n++] = all;
12         for(h = 0; h < n-1; h++)
13             if(all == cou[h])
14             break;
15         if(h == n-1)
16                 a++;
17         return ;
18     }
19 for(int i = 0; i < 4; i++)
20     {
21         int xn = x + x1[i], yn = y + y1[i];
22         if(xn >= 0 && xn <= 4 && yn >= 0 && yn <= 4)
23             {
24             dfs(xn, yn, c + 1, all * 10 + map1[xn][yn]);
25             }
26     }
27 return ;
28 }
29 
30 int main()
31 {
32     a = 0;
33     n = 0;
34     for(int i = 0; i < 5; i++)
35         for(int k = 0; k < 5; k++)
36         cin >> map1[i][k];
37     for(int i = 0; i < 5; i++)
38         for(int k = 0; k < 5; k++)
39         dfs(i, k, 1, map1[i][k]);
40     cout << a << endl;
41     return 0;
42 }

POJ3050

 1 #include <iostream>
 2 #include <bitset>
 3 using namespace std;
 4 
 5 bitset<10000> map1[10];
 6 int r,c,cou;
 7 
 8 void dfs(int all){
 9     if(all == r)
10         {
11             int num, upcou=0;
12             for(int i = 0; i < c; i++)
13                 {
14                     num=0;
15                     for(int k = 0; k < r; k++)//竖向翻转取大的
16                     if(map1[k][i])
17                     num++;
18                     upcou += max(num, r-num);
19                 }
20             cou = max(cou, upcou);
21             return;
22         }
23     dfs(all+1);//所有情况
24     map1[all].flip();
25     dfs(all+1);
26     return ;
27 }
28 int main()
29 {
30     while(cin >> r >> c)//r行c列
31     {
32         if(r == 0 && c == 0)
33             break;
34      for(int i = 0,g; i < r; i++)
35         for(int k = 0; k < c; k++)
36             {
37             cin >> g;
38             map1[i][k]=g;
39             }
40         cou = 0;
41         dfs(0);
42         cout << cou <<endl;
43     }
44     return 0;
45 }

AOJ0525 CN

2.2 贪心

区间

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 25000;
 6 pair<int, int> line[maxn];
 7 int g,h,N,T,j,maxitime;
 8 
 9 int main()
10 {
11      int i, t, cou = 0;
12      cin >> N >> T;
13      for(i = 0; i < N; i++)
14         cin >> line[i].first >> line[i].second;
15      sort(line, line + N);//排序，按照开始时间>>结束时间
16 
17      if(line[0].first != 1) printf("-1\n");//不是从1开始则失败
18      else
19         {
20             t=line[0].second;
21             i = 1;
22             while(line[i].first == 1) t = line[i++].second;//取得第一段结束时间最晚的
23             cou = 1;
24 
25             while(t < T)//后面的段
26             {
27                 if(i >= N)break;
28                 j = i;
29                 maxitime=line[i].second;
30                 i++;
31                 while( i < N && line[i].first <= t+1)//往后取，直到取尽或者不连续
32                 {
33                     if(line[i].second > maxitime)
34                         {
35                             maxitime=line[i].second;//取得每一段结束时间最晚的
36                             j=i;//j是有效的段
37                         }
38                     i++;//往后取
39                 }
40                 if(maxitime <= t || line[j].first > t+1) break;//不能取完或是非正常区域内的段
41                 else
42                     {
43                      cou++;
44                      t = line[j].second;//更新结束时间
45                     }
46             }
47             if(t<T) printf("-1\n");
48             else printf("%d\n",cou);
49         }
50     return 0;
51 }

POJ2376

 1 #include <iostream>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 bool flag;
 7 int ans,T = 0,head,tail,n,d,a,b;
 8 
 9 struct point{
10     double x,y;
11     point(double a = 0, double b = 0){ x = a, y = b; }
12     bool operator < (const point c)const {return x < c.x;}
13 }queue1[1005];
14 
15 void push(point v){queue1[tail++]=v;}
16 void pop(){head++;}
17 
18 bool judge(point &t,point v){
19 if(!( t.x>v.y || t.y< v.x))
20     {
21      t.x = min(t.x,v.x);
22      t.y = min(t.y,v.y);
23      return true;
24     }
25 return false;
26 }
27 
28 int main()
29 {
30     while(cin >> n >> d)
31     {
32         if(!n && !d) break;
33         ans = flag = head = tail = 0;
34             for(int i = 0; i < n; i++)
35         {
36             cin >> a >> b;
37             if(b > d) flag = 1;
38             else
39             {
40                 push(point(a-sqrt((double)d*d - b*b),a+sqrt((double)d*d - b*b)));
41             }
42         }
43         if(flag) cout << "Case " << ++T << ": " << "-1" <<endl;
44         else
45         {
46             sort(queue1, queue1 + n);
47             while(head != tail)
48             {
49                 ans++;
50                 point t = queue1[head];
51                 while(head != tail)
52                 {
53                     point v = queue1[head];
54                     if(judge(t,v)) pop();
55                     else break;
56                 }
57             }
58             cout << "Case " << ++T << ": " << ans <<endl;
59         }
60     }
61     return 0;
62 }

POJ1328

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int N,house[50005];
 7 
 8 struct stu{
 9     int a,b,site;
10 
11     bool operator < (const stu &a1) const {
12     if(b == a1.b) return a > a1.a;
13     else return b > a1.b;
14     }
15 } line[50005];
16 
17 priority_queue<stu> que;
18 
19 bool cmp(stu a1, stu b1){
20     if(a1.a > b1.a) return false;
21     if(a1.a < b1.a) return true;
22     else return a1.b < b1.b;
23 }
24 
25 
26 int main()
27 {
28     while(cin >> N)
29         {
30             for(int i = 0; i < N; i++)
31                 {
32                     cin >> line[i].a >> line[i].b;
33                     line[i].site = i;
34                 }
35         sort(line, line + N, cmp);
36 
37         int cou=1;
38         house[line[0].site] = 1;
39         que.push(line[0]);
40         for(int i = 1; i < N; i++)
41             {
42              if(!que.empty() && que.top().b < line[i].a)
43              {
44                  house[line[i].site] = house[que.top().site];
45                  que.pop();
46              }
47              else
48              {
49                  cou++;
50                  house[line[i].site] = cou;
51              }
52              que.push(line[i]);
53             }
54 
55             cout << cou <<endl;
56             for(int i = 0; i < N; i++)
57                 cout << house[i] <<endl;
58             while(!que.empty())
59                 que.pop();
60         }
61     return 0;
62 }

POJ3190

2.5 图

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n,w,m,d[520],num,s,e,t;
 5 struct edge{
 6     int from, to, cost;
 7 }eg[5203];
 8 
 9 bool shortpath(){
10     bool flag;
11     d[1] = 0;
12     for(int i = 1; i < n; i++)
13     {
14         flag = false;
15         for(int j = 0; j < num; j++)
16             if(d[eg[j].from] + eg[j].cost < d[eg[j].to])
17             {
18                 d[eg[j].to] = d[eg[j].from] + eg[j].cost;
19                 flag = true;
20             }
21         if(!flag)
22             return false;
23     }
24     for(int i = 0; i < num; i++)
25         if(d[eg[i].from] + eg[i].cost < d[eg[i].to])
26         return true;
27 
28 }
29 
30 int main()
31 {
32     int T;
33     cin >> T;
34         while(T--)
35     {
36         num = 0;
37         cin >> n >> m >> w;
38         for(int i = 0; i < m; i++)
39         {
40             cin >> s >> e >> t;
41             eg[num].from = s;
42             eg[num].to = e;
43             eg[num++].cost = t;
44             eg[num].from = e;
45             eg[num].to = s;
46             eg[num++].cost = t;
47         }
48         for(int i = 0; i < w; i++)
49         {
50             cin >> s >> e >> t;
51             eg[num].from = s;
52             eg[num].to = e;
53             eg[num++].cost = -t;
54         }
55         for(int i = 1; i <= n; i++)
56             d[i]=0x3f3f3f3f;
57         if(shortpath())
58             cout << "YES" <<endl;
59         else cout << "NO" << endl;
60     }
61     return 0;
62 }

POJ3259

挑战程序系列

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 挑战程序系列

挑战程序系列

看完仍有疑问？有类似问题直接问程序猿