Submission #36256

#	Time	Username	Problem	Language	Result	Execution time	Memory
36256		Flumen	Price List (POI13_cen)	C++11	100 / 100	233 ms	14676 KiB

cen

#include<bits/stdc++.h>
using namespace std;
vector<int>node[100100],node1[100100],tmp;
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<node1[x].size();i++){
            for(int j=0;j<node[node1[x][i]].size();j++){
                z=lower_bound(node1[node[node1[x][i]][j]].begin(),node1[node[node1[x][i]][j]].end(),x)-node1[node[node1[x][i]][j]].begin();
                if(mark[node[node1[x][i]][j]]==2)tmp.push_back(node[node1[x][i]][j]);
                else if(z<node1[node[node1[x][i]][j]].size()&&node1[node[node1[x][i]][j]][z]==x)tmp.push_back(node[node1[x][i]][j]);
                else{
                    mark[node[node1[x][i]][j]]=2;
                    Q.push(make_pair(node[node1[x][i]][j],y+1));
                }
            }
            node[node1[x][i]].clear();
            for(int j=0;j<tmp.size();j++){
                node[node1[x][i]].push_back(tmp[j]);
            }
            tmp.clear();
        }
    }
}
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);
        node1[x].push_back(y);
        node1[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        sort(node[i].begin(),node[i].end());
        sort(node1[i].begin(),node1[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 (stderr)

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<node1[x].size();i++){
                      ^
cen.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<node[node1[x][i]].size();j++){
                          ^
cen.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 else if(z<node1[node[node1[x][i]][j]].size()&&node1[node[node1[x][i]][j]][z]==x)tmp.push_back(node[node1[x][i]][j]);
                          ^
cen.cpp:39:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<tmp.size();j++){
                          ^
cen.cpp: In function 'int main()':
cen.cpp:48: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:51: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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10