Well, I searched trying to find an answer for this problem : http://ift.tt/1wqje1m Actually I found some of them, but I'm still curious about this one which is wrong, Here's the code:
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
using size_type = unsigned long long int;
using ushort = unsigned short;
class Node
{
public :
void addEdge(ushort e) {_edges.push_back(e);}
const ushort &operator[] (int n) const {return _edges[n];}
ushort size() const {return _edges.size();}
void clear() {_edges.clear();}
private :
vector<ushort> _edges;
};
class Map
{
public :
Map() : _C{0}, _B{0}, _S{0}, _T{0} {}
Node& operator[] (const ushort i) {return _Node[i];}
const Node& operator[] (const ushort i) const {return _Node[i];}
friend istream &operator>> (istream &is, Map &m);
ushort C() {return _C;}
ushort B() {return _B;}
ushort start() {return _S;}
ushort end() {return _T;}
private :
void _reset();
Node _Node[10000];
ushort _C, _B, _S, _T;
};
void Map::_reset()
{
for (ushort i = 0; i < _C; i++)
_Node[i].clear();
}
istream &operator>>(istream &is, Map &m)
{
m._reset();
ushort x, y;
scanf("%hu %hu %hu %hu", &m._C, &m._B, &m._S, &m._T);
m._S--; m._T--;
for (ushort i = 0; i < m._B; i++)
{
scanf("%hu %hu", &x, &y);
x--; y--;
m[x].addEdge(y);
}
return is;
}
size_type paths(Map &m);
void count(Map &m, ushort p, map<ushort, size_type> &h);
int main()
{
Map m;
ushort D;
scanf("%hu", &D);
while (D--)
{
cin >> m;
printf("%I64u\n", paths(m) % 1000000007LL);
}
}
size_type paths(Map &m)
{
if (m.start() == m.end()) return 1;
map<ushort, size_type> h;
h[m.end()] = 1;
count(m, m.start(), h);
return h[m.start()];
}
void count(Map &m, ushort p, map<ushort, size_type> &h)
{
for (ushort i = 0; i < m[p].size(); i++)
{
if (h.find(m[p][i]) == h.end())
count(m, m[p][i], h);
h[p] += h[m[p][i]];
}
}
I simply try to use memorization to count number of paths, but wherever I go, they talk about topological sort.. etc. why this code fragment is still giving a wrong answer ? why is it not sufficient ?
Thanks - Sam
Aucun commentaire:
Enregistrer un commentaire