#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e4+5;
vector<int> graf[maxn];
ll N,M,K,poz[maxn],res[maxn],dist[maxn],d1[maxn],d2[maxn],cena[maxn],propval[maxn];
bool nexttostop[maxn];
int prosli[maxn],pvred;
string stop;
priority_queue<pair<ll,ll>> PQ;
queue<pair<int,int>> Q;
void input(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M>>K;
while(M--){
int a,b;
cin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
cin>>stop;
stop="0"+stop+"0000";
for(int i=0;i<stop.size();i++)
stop[i]-='0';
for(int i=1;i<=K;i++)
cin>>poz[i];
}
void BFS(bool props=true){
for(int i=1;i<=N;i++)
dist[i]=1e18;
while(Q.size()){
auto x=Q.front();
Q.pop();
int tren=x.first;
int d=x.second;
if(dist[tren]!=1e18)
continue;
dist[tren]=d;
if(stop[tren] and props==false)
continue;
for(int y:graf[tren])
Q.push({y,d+1});
}
}
void solve1(){
int poc=poz[1];
Q.push({poc,0});
BFS();
for(int i=1;i<=N;i++)
cout<<dist[i]<<"\n";
}
void calcdist(){
for(int i=1;i<=N;i++){
nexttostop[i]=false;
for(int x:graf[i])
nexttostop[i]|=stop[x];
}
for(int i=1;i<=K;i++){
int poc=poz[i];
d1[poc]=1e18;
Q.push({poc,0});
BFS();
for(int j=1;j<=N;j++)
if(stop[j]==1)
d1[poc]=min(d1[poc],dist[j]);
if(d1[poc]==0)
if(nexttostop[poc])
d1[poc]=1;
else
d1[poc]=2;
}
for(int i=1;i<=N;i++)
d2[i]=1e18;
for(int i=1;i<=N;i++)
if(nexttostop[i] and stop[i])
PQ.push({-1,i});
pvred++;
while(PQ.size()){
auto aa=PQ.top();
PQ.pop();
int tren=aa.second;
int d=-aa.first;
if(prosli[tren]==pvred)
continue;
prosli[tren]=pvred;
d2[tren]=d;
for(int x:graf[tren])
PQ.push({-(d+1-stop[tren]),x});
}
}
void calcchange(){
for(int i=2;i<=K;i++){
int x=poz[i];
for(int i=1;i<=N;i++)
cena[i]+=min(d1[x]+2*(i-1),d2[x]+(i-1));
}
for(int i=N;i>=2;i--)
cena[i]-=cena[i-1];
}
void Dijkstra(){
pvred++;
while(PQ.size()){
auto aa=PQ.top();
PQ.pop();
int tren=aa.second;
ll d=-aa.first;
if(prosli[tren]==pvred)
continue;
// cout<<tren<<" "<<d<<endl;
prosli[tren]=pvred;
dist[tren]=min(dist[tren],d);
if(stop[tren] and propval[tren]!=d)
continue;
for(int x:graf[tren])
PQ.push({-(d+1),x});
}
}
int main(){
input();
bool hasstop=false;
for(int i=1;i<=N;i++)
if(stop[i])
hasstop=true;
if(hasstop==false){
solve1();
return 0;
}
calcdist();
// cout<<"AAA"<<endl;
calcchange();
//cout<<"BB"<<endl;
/* cout<<"CENE"<<endl;
for(int i=1;i<=N;i++)
cout<<cena[i]<<" ";
cout<<endl;
*/
for(int i=1;i<=N;i++)
dist[i]=res[i]=1e18;
int poc=poz[1];
//dist[poc]=res[poc]=0;
for(int i=1;i<=N;i++)
propval[i]=-1;
propval[poc]=0;
PQ.push({0,poc});
Dijkstra();
/* for(int i=1;i<=N;i++)
cout<<dist[i]<<" ";
cout<<endl;
*/
for(int i=1;i<=N;i++)
res[i]=min(dist[i],res[i]);
for(int it=1;it<=10;it++){
for(int i=1;i<=N;i++)
propval[i]=-1;
for(int i=1;i<=N;i++)
if(stop[i] and dist[i]<1e17){
ll d=dist[i]+cena[it];
PQ.push({-d,i});
propval[i]=d;
}
for(int i=1;i<=N;i++)
dist[i]=1e18;
Dijkstra();
for(int i=1;i<=N;i++)
res[i]=min(dist[i],res[i]);
}
for(int i=1;i<=N;i++)
cout<<res[i]<<"\n";
return 0;
}
Compilation message
Main.cpp: In function 'void input()':
Main.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i=0;i<stop.size();i++)
| ~^~~~~~~~~~~~
Main.cpp: In function 'void calcdist()':
Main.cpp:67:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
67 | if(d1[poc]==0)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
14 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
17 ms |
5976 KB |
Output is correct |
| 4 |
Correct |
15 ms |
5676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
3816 KB |
Output is correct |
| 2 |
Execution timed out |
4043 ms |
4952 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
3816 KB |
Output is correct |
| 2 |
Execution timed out |
4082 ms |
4956 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
34 ms |
3796 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
3676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
5980 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
7508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
5980 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
7508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
34 ms |
3796 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
3676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
14 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
17 ms |
5976 KB |
Output is correct |
| 4 |
Correct |
15 ms |
5676 KB |
Output is correct |
| 5 |
Correct |
227 ms |
3816 KB |
Output is correct |
| 6 |
Execution timed out |
4043 ms |
4952 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
