interview street: zombie march, page rank

ZombieMarch.cpp

/*
 * https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
 * http://www.17sotv.com/ 17sotv电影天堂
 */
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 100000
#define PAGE_RANK_ITERATION_ROUND 50

int n, m, k;
vector<int> edges[MAXN];
double val[2][MAXN];

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        while (m--)
        {
            int i, j;
            scanf("%d%d", &i, &j);
            edges[i].push_back(j);
            edges[j].push_back(i);
        }
        for (int i = 0; i < n; ++i)
        {
            scanf("%lf", &val[0][i]);
        }
        k = min(k, PAGE_RANK_ITERATION_ROUND);
        int now = 0, next = 1;
        while (k--)
        {
            for (int i = 0; i < n; ++i)
            {
                val[next][i] = 0;
                for (int j = 0; j < edges[i].size(); ++j)
                {
                    int p = edges[i][j];
                    val[next][i] += val[now][p] / edges[p].size();
                }
            }
            now = 1 - now;
            next = 1 - next;
        }
        sort(val[now], val[now] + n);
        for (int i = n - 1; i >= n - 5; --i)
        {
            int j = int(val[now][i]);
            if (val[now][i] - j >= 0.5)
            {
                j++;
            }
            printf("%d ", j);
        }
        printf("\n");
        for (int i = 0; i < n; ++i)
        {
            edges[i].clear();
        }
    }
    return 0;
}

ZombieMarch.py

#!/usr/bin/python

"""
 https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
 http://www.17sotv.com/ 17sotv电影天堂
"""

import sys
import random
import time

page_rank_iteration_round = 50

def main():
    # read t
    line = sys.stdin.readline().strip()
    t = int(line)
    while t > 0:
        t = t - 1
        # test time
        # print "start: %d" % time.time()
        # read n, m, k
        line = sys.stdin.readline().strip()
        (n, m, k) = (int(i) for i in line.split())
        # define node degree, and edges
        degree = [0] * n
        edges = [[] for i in xrange(0, n)]
        # read edges
        for i in xrange(0, m):
            line = sys.stdin.readline().strip()
            (p, q) = (int(x) for x in line.split())
            degree[p] = degree[p] + 1
            degree[q] = degree[q] + 1
            edges[p].append(q)
            edges[q].append(p)
        # define zombie number
        num = [[0.0] * n for i in xrange(0, 2)]
        # read initial zombie number
        for i in xrange(0, n):
            line = sys.stdin.readline().strip()
            num[0][i] = float(line)
        # end input time
        # print "end input: %d" % time.time()
        # enumarate the process
        k = min(k, page_rank_iteration_round)
        (now, next) = (0, 1)
        while k > 0:
            k = k - 1
            for i in xrange(0, n):
                num[next][i] = 0
                for j in edges[i]:
                    num[next][i] = num[next][i] + num[now][j] / degree[j]
            (now, next) = (1 - now, 1 - next)
        # sort the result
        num[now].sort(reverse = True)
        # end compute time
        # print "end compute: %d" % time.time()
        # output the result
        for i in num[now][0:5]:
            print int(round(i)),
        print

if __name__ == '__main__':
    main()

ZombieMarch_v2.py

#!/usr/bin/python

"""
 https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
 http://www.17sotv.com/ 17sotv电影天堂
"""

import sys
import random
import time

page_rank_iteration_round = 50

def main():
    # read t
    line = sys.stdin.readline()
    t = int(line)
    for _ in range(t):
        # test time
        # print "start: %d" % time.time()
        # read n, m, k
        line = sys.stdin.readline().strip()
        (n, m, k) = (int(i) for i in line.split())
        # define node degree, and edges
        degree = [0] * n
        edges = [[] for i in xrange(0, n)]
        # read edges
        for i in xrange(0, m):
            line = sys.stdin.readline()
            (p, q) = (int(x) for x in line.split())
            degree[p] += 1
            degree[q] += 1
            edges[p].append(q)
            edges[q].append(p)
        # define zombie number
        num = [[0.0] * n for i in xrange(0, 2)]
        # read initial zombie number
        for i in xrange(0, n):
            line = sys.stdin.readline()
            num[0][i] = float(line)
        # end input time
        # print "end input: %d" % time.time()
        # enumarate the process
        k = min(k, page_rank_iteration_round)
        now, next_ = 0, 1
        for _ in range(k):
            for i in xrange(0, n):
                num[next_][i] = 0
                for j in edges[i]:
                    num[next_][i] = num[next_][i] + num[now][j] / degree[j]
            now, next_ = next_, now
        # sort the result
        num[now].sort(reverse = True)
        # end compute time
        # print "end compute: %d" % time.time()
        # output the result
        for i in num[now][0:5]:
            print int(round(i)),
        print

if __name__ == '__main__':
    main()

the cpp code can pass all the test cases, but the python code will fail the 7th test case (Time Limit Exceed), who can help to improve this python code, and give some advise on writing optimized python code.