Тема: Timus 1930
How can I quickly build adjacency matrix befor using bfs for this problem. I have TLE#6,#10,#12 for this problem. Any algorithm please!
Re: Timus 1930
Why do you need adjacency matrix: it'll occupy 10000x10000 = 100M values? Use adjacency lists instead, their total size will be exactly 2*m.
Re: Timus 1930
But problem with time.
This my code.
// timus1930.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <bitset>
#include <set>
#define MAXV 10001
using namespace std;
typedef vector<short> vi;
typedef bitset<MAXV+1> bits;
bits edges[MAXV+1];
int parent[MAXV+1];
bool visited[MAXV+1];
int n,m;
void BFS(int vertex)
{
queue <int> q;
q.push(vertex);
visited[vertex]=true;
while(!q.empty())
{
vertex=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(edges[vertex][i])
{
int vert=i;
if(visited[vert]==false)
{
visited[vert]=true;
parent[vert]=vertex;
q.push(vert);
}
}
}
}
}
int main()
{
int a,b;
scanf("%d %d",&n,&m);
set <int> *baland=new set<int>[n+1];
set <int> *past=new set<int>[n+1];
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
for(set <int>::iterator ite=past[a].begin();ite!=past[a].end();ite++)
{
past[b].insert(*ite);
}
past[b].insert(a);
for(set<int>::iterator ite=baland[b].begin();ite!=baland[b].end();ite++)
{
baland[a].insert(*ite);
}
edges[a][b]=true;
edges[b][a]=true;
}
int nach,kon;
cin>>nach>>kon;
if(nach==kon)
{
cout<<"0"; return 0;
}
BFS(nach);
int changes=0;
for(int i=kon;parent[i];i=parent[i],changes++);
changes--;
cout<<changes;
return 0;
}Re: Timus 1930
You should build a graph with 2 * N vertices: two vertices for each city (encoding which gear-mode is currently selected: for moving up or moving down).
UPD The edges in this new graph will have costs either 0 or 1, depending on whether we have to switch a gear-mode or not.
Re: Timus 1930
I realize this but got WA#11. I can't find my mistake.
Please help me.
#include <iostream>
#include <algorithm>
#include <list>
#define MAXV 10001
#define INF 1000000000
using namespace std;
typedef list<int> L;
struct Graph
{
L edges[2*(MAXV+1)];
int nvert;
}graph;
int parent[MAXV+1];
int distance_[MAXV+1];
bool svyaz[MAXV+1];
bool intree[MAXV+1];
void dijkstra(int start)
{
int weight,w,v,dist;
for(int i=1;i<=graph.nvert;i++)
{
distance_[i]=INF;
parent[i]=-1;
}
distance_[start]=0;
v=start;
while(intree[v]==false)
{
intree[v]=true;
if(svyaz[v]) weight=0;
else weight=1;
if(v==start) weight=0;
for(L::iterator i=graph.edges[2*v-1].begin();i!=graph.edges[2*v-1].end();i++)
{
w=*i;
if(distance_[w]>(distance_[v]+weight))
{
distance_[w]=distance_[v]+weight;
parent[w]=v;
svyaz[w]=true;
}
}
if(svyaz[v]) weight=1;
else weight=0;
if(v==start) weight=0;
for(L::iterator i=graph.edges[2*v].begin();i!=graph.edges[2*v].end();i++)
{
w=*i;
if(distance_[w]>(distance_[v]+weight))
{
distance_[w]=distance_[v]+weight;
parent[w]=v;
svyaz[w]=false;
}
}
v=1;
dist=INF;
for(int i=1;i<=graph.nvert;i++)
{
if((intree[i]==false)&&(dist>distance_[i]))
{
dist=distance_[i];
v=i;
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
graph.edges[2*a-1].push_back(b);
graph.edges[2*b].push_back(a);
}
graph.nvert=n;
int nach,kon;
cin>>nach>>kon;
if(nach==kon)
{
cout<<"0"; return 0;
}
dijkstra(nach);
cout<<distance_[kon];
return 0;
}