oj.uz

답안 #36242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36242 2017-12-06T13:49:18 Z Flumen Price List (POI13_cen) C++11
70 / 100
 4000 ms 8912 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int>node[100100];
int ans[100100],mark[100100];
queue<pair<int,int> >Q;
void bfs1(int k,int a,int b){
    Q.push(make_pair(k,0));
    while(!Q.empty()){
        mark[Q.front().first]=1;
        ans[Q.front().first]=min(b,2*a)*(Q.front().second/2)+a*(Q.front().second%2);
        for(int i=0;i<node[Q.front().first].size();i++){
            if(mark[node[Q.front().first][i]]==1)continue;
            mark[node[Q.front().first][i]]=1;
            Q.push(make_pair(node[Q.front().first][i],Q.front().second+1));
        }
        Q.pop();
    }
}
void bfs2(int k,int a,int b){
    int x,y,z;
    Q.push(make_pair(k,0));
    while(!Q.empty()){
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        mark[x]=2;
        ans[x]=min(ans[x],min(y*b,y*2*a));
        for(int i=0;i<node[x].size();i++){
            for(int j=0;j<node[node[x][i]].size();j++){
                if(mark[node[node[x][i]][j]]==2)continue;
                z=lower_bound(node[node[node[x][i]][j]].begin(),node[node[node[x][i]][j]].end(),x)-node[node[node[x][i]][j]].begin();
                if(z<node[node[node[x][i]][j]].size()&&node[node[node[x][i]][j]][z]==x)continue;
                mark[node[node[x][i]][j]]=2;
                Q.push(make_pair(node[node[x][i]][j],y+1));
            }
        }
    }
}
int main(){
    int n,m,k,a,b,i,x,y;
    scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        node[x].push_back(y);
        node[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        sort(node[i].begin(),node[i].end());
    }
    bfs1(k,a,b);
    bfs2(k,a,b);
    for(i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

Compilation message

cen.cpp: In function 'void bfs1(int, int, int)':
cen.cpp:11:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<node[Q.front().first].size();i++){
                      ^
cen.cpp: In function 'void bfs2(int, int, int)':
cen.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<node[x].size();i++){
                      ^
cen.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<node[node[x][i]].size();j++){
                          ^
cen.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(z<node[node[node[x][i]][j]].size()&&node[node[node[x][i]][j]][z]==x)continue;
                     ^
cen.cpp: In function 'int main()':
cen.cpp:41:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
                                       ^
cen.cpp:44:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 0 ms 5148 KB Output is correct
3 Correct 0 ms 5148 KB Output is correct
4 Correct 0 ms 5148 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 0 ms 5148 KB Output is correct
3 Correct 3 ms 5148 KB Output is correct
4 Correct 0 ms 5148 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 0 ms 5148 KB Output is correct
3 Correct 0 ms 5148 KB Output is correct
4 Correct 0 ms 5148 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 5544 KB Output is correct
2 Correct 36 ms 5544 KB Output is correct
3 Correct 13 ms 5544 KB Output is correct
4 Correct 13 ms 5544 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 996 ms 6732 KB Output is correct
2 Correct 1063 ms 6732 KB Output is correct
3 Correct 39 ms 6072 KB Output is correct
4 Correct 56 ms 6468 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1069 ms 7696 KB Output is correct
2 Correct 406 ms 7300 KB Output is correct
3 Correct 79 ms 7392 KB Output is correct
4 Correct 89 ms 7392 KB Output is correct
5 Correct 2983 ms 8056 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1756 ms 8112 KB Output is correct
2 Correct 169 ms 7284 KB Output is correct
3 Correct 103 ms 7524 KB Output is correct
4 Correct 126 ms 7392 KB Output is correct
5 Correct 3966 ms 8444 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1159 ms 8604 KB Output is correct
2 Correct 409 ms 8080 KB Output is correct
3 Correct 103 ms 7788 KB Output is correct
4 Correct 116 ms 7392 KB Output is correct
5 Execution timed out 4000 ms 8720 KB Execution timed out

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 8200 KB Output is correct
2 Correct 379 ms 8200 KB Output is correct
3 Correct 133 ms 7788 KB Output is correct
4 Correct 109 ms 7392 KB Output is correct
5 Execution timed out 4000 ms 8876 KB Execution timed out

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 8316 KB Output is correct
2 Correct 113 ms 8184 KB Output is correct
3 Correct 156 ms 8316 KB Output is correct
4 Correct 103 ms 7392 KB Output is correct
5 Execution timed out 4000 ms 8912 KB Execution timed out