fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // #define int long long
  5. using ll = long long;
  6. using ld = long double;
  7. #define el '\n'
  8. #define dbg(x) cout << #x << " = " << x << el
  9.  
  10. const int N=1e5+10;
  11. const ll INF=2e18;
  12. vector<ll> adj[N], cores(N), vis(N), peso(N), dist(N, INF);
  13.  
  14. void solve() {
  15.     int n, m, k; cin >> n >> m >> k;
  16.     for(int i = 1; i<= n; i++){
  17.         int a; cin >>a; peso[i]=a;
  18.     }
  19.     for(int i =0; i<m; i++){
  20.         int a, b; cin >>a >> b;
  21.         adj[a].push_back(b);
  22.         adj[b].push_back(a);
  23.     }
  24.  
  25.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  26.  
  27.     pq.push(make_pair(peso[1], 1));
  28.     while (!pq.empty())
  29.     {
  30.         auto [p, v] = pq.top();
  31.         pq.pop();
  32.         if(vis[v]) continue;
  33.         vis[v]=1;
  34.  
  35.         for(auto x: adj[v]){
  36.             if(vis[x] || dist[x] < peso[x] + p) continue;
  37.             dist[x] = peso[x]+p;
  38.             pq.push({peso[x]+p, x});
  39.         }
  40.     }
  41.  
  42.     set <int> st;
  43.     for(int i = 1; i<= n; i++) st.insert(i);
  44.     int flag = 0, comp= n-k;
  45.     for(auto x:adj[1]) if(x == n) flag = 1;
  46.  
  47.     if(flag && dist[n] == peso[1] + peso[n] && k == 1 && comp == 1){
  48.         cout << "impossible\n";
  49.         return;
  50.     } else if(flag && dist[n] == peso[1] + peso[n]){
  51.         if(k > 1){
  52.             cores[1] = cores[n] = 1;k-=2;
  53.             st.erase(1); st.erase(n);
  54.         } else{
  55.             cores[1] = cores[n] = 2;
  56.             st.erase(1); st.erase(n);
  57.         }
  58.     }
  59.  
  60.     // cout << dist[n]<<"\n";
  61.  
  62.  
  63.     if(k >= 1){
  64.         if(st.find(1) != st.end()){
  65.             k--;
  66.             cores[1] = 1;
  67.             st.erase(1);
  68.         }
  69.  
  70.         for(auto x: adj[1]){
  71.             if(!k) break;
  72.             cores[x] = 1;
  73.             k--;
  74.             st.erase(x);
  75.         }
  76.     }
  77.  
  78.     if(k >= 1){
  79.         if(st.find(n) != st.end()){
  80.             k--;
  81.             cores[n] =1;
  82.             st.erase(n);
  83.         }
  84.  
  85.         for(auto x: adj[n]){
  86.             if(!st.size() || st.find(x) == st.end()) continue;
  87.             if(!k) break;
  88.             k--;
  89.             st.erase(x);
  90.         }
  91.     }
  92.  
  93.     for(auto x: st) cores[x] = 2;
  94.     for(int i = 1; i<= n; i++){
  95.         if(cores[i] == 2) cout << "S";
  96.         else cout <<"N";
  97.     }
  98.     cout <<"\n";
  99.  
  100.  
  101. }
  102.  
  103. int32_t main() {
  104.     ios::sync_with_stdio(false);
  105.     cin.tie(nullptr);
  106.  
  107.     int ttt = 1;
  108.     // cin >> ttt;
  109.     while(ttt--) {
  110.         solve();
  111.     }
  112.     return 0;
  113. }
Success #stdin #stdout 0.01s 8488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/retnH1
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
21 hours ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!