| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429571 |
2021-06-16T06:53:40 Z |
장태환(#7566) |
Brackets (CPSPC17_brackets) |
C++17 |
|
3 ms |
588 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
set<pair<int,pair<int,int>>>pq;
vector<pair<int,char>>link[201];
vector<pair<int,char>>rev[201];
int dist[21][21];
int vis[21][21];
signed main()
{
memset(dist,62,sizeof(dist));
int N,M,s,t;
cin >> N>>M>>s>>t;
int i;
for(i=0;i<M;i++)
{
int a,b;
char d;
cin >>a >> b >> d;
link[a].push_back({b,d});
rev[b].push_back({a,d});
}
for(i=1;i<=N;i++)
pq.insert({0,{i,i}});
while(pq.size())
{
auto r=*pq.begin();
pq.erase(r);
if(vis[r.second.first][r.second.second])
continue;
dist[r.second.first][r.second.second]=r.first;
vis[r.second.first][r.second.second]=1;
for(i=1;i<=N;i++)
{
if(dist[r.second.first][r.second.second]+dist[r.second.second][i]<dist[r.second.first][i])
{
pq.erase({dist[r.second.first][i],{r.second.first,i}});
dist[r.second.first][i]=dist[r.second.first][r.second.second]+dist[r.second.second][i];
pq.insert({dist[r.second.first][i],{r.second.first,i}});
}
if(dist[r.second.first][r.second.second]+dist[i][r.second.first]<dist[i][r.second.second])
{
pq.erase({dist[i][r.second.second],{i,r.second.second}});
dist[i][r.second.second]=dist[r.second.first][r.second.second]+dist[i][r.second.first];
pq.insert({dist[i][r.second.second],{i,r.second.second}});
}
}
for(i=0;i<rev[r.second.first].size();i++)
{
int j;
for(j=0;j<link[r.second.second].size();j++)
{
auto r1=rev[r.second.first][i];
auto r2=link[r.second.second][j];
if(r1.second==r2.second||abs(r1.second-r2.second)>2)
continue;
if(dist[r.second.first][r.second.second]+2<dist[r1.first][r2.first])
{
pq.erase({dist[r1.first][r2.first],{r1.first,r2.first}});
dist[r1.first][r2.first]=dist[r.second.first][r.second.second]+2;
pq.insert({dist[r1.first][r2.first],{r1.first,r2.first}});
}
}
}
}
if(!vis[s][t])
cout <<-1;
else
cout <<dist[s][t];
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:48:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(i=0;i<rev[r.second.first].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(j=0;j<link[r.second.second].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
