10986 - Sending email

[avdtech]

Just a little correction in the test cases posted by neilor -

TC#66 is wrong -

it should be
3 1 0 2
0 2 103

instead of
2 1 0 2
0 2 103

since the nodes are number from 0 to n-1.

Thanks for the cases. It helped a lot.

[DD]

Hello People.

Follow some test cases to the problem (test using uva tookit: http://uvatoolkit.com/problemssolve.php)

Code: Select all

75

6 3 0 2
0 1 50
2 1 70
0 2 150

2 1 0 1
1 0 33333

2 0 0 0

2 1 0 1
1 0 111

2 2 0 1
1 0 100
0 1 33

2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1



14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7

4 5 0 3
0 2 17
0 3 18
2 3 11
2 1 2
0 1 4

4 7 0 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

4 7 2 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

14 20 13 2
0 1 123
1 2 4567
2 3 4578
4 5 5678
5 3 47
2 6 256
7 2 2346
5 9 2345
5 3 12345
8 2 5785
9 4 2345
2 8 4367
9 12 3467
13 7 5687
11 9 4576
9 5 34
11 13 345
13 11 2
12 11 7
12 6 235898

14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7


6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 3 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 1 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 2 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4


5 5 0 4
0 1 3
1 0 2
1 0 1
0 1 4
1 4 1000

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 4 3
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 13 0 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 1 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 3 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 5 0
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

4 3 0 2
0 1 50
2 1 70
0 2 150

4 3 1 2
0 1 50
2 1 70
0 2 150

6 9 5 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 6 4
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 5
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
4 3 404
2 3 505
1 2 606
0 1 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
1 2 505
2 3 606
3 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
3 2 505
2 1 606
5 6 303
4 5 100
3 4 201
6 7 707

8 7 0 7
4 3 404
4 5 505
5 6 606
3 2 303
2 1 100
6 7 201
0 1 707

8 7 0 7
1 2 404
6 7 505
3 4 606
0 1 303
5 4 100
5 6 201
3 2 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
2 3 404
1 2 505
0 1 606
4 0 303
5 4 100
6 5 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 0 5
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

6 3 0 2
0 1 50
2 1 70
0 2 150


2 1 0 1
1 0 33333

2 1 0 2
0 2 103

2 0 0 1

2 0 1 2

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 100
0 2 200
1 2 50

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 102
0 2 202
1 2 52

4 3 1 0
1 2 104
2 3 204
0 3 54

Thank you for providing the test case

[LeonardoB]

Hi.

I got tle in this problem using Dijkstra algorithm and priority queu.

Code: Select all

include <cstdlib>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <list>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <limits>
#include <cctype>
#include <queue>

using namespace std;

class Graph {

private:
	struct Node;

	class compare {

	private:
		int * dist;

	public:
		compare (int * d) : dist(d) {}
		bool operator () (const Node* n1, const Node* n2) {

			return dist[n1->id] < dist[n2->id];
		}
	};

	struct Edge {

		Node * begin, * end;
		int value;
		friend bool operator < (const Edge & e1, const Edge & e2) {
			return e1.value < e2.value;
		}
	};

	struct Node {
		
	public:
		
		int id;
		vector<Edge> next;
		bool visited;
	};

	Node* nodes;
	int* dist;
	int N;

public:
	
	Graph (int k) {
		N = k;
		nodes = new Node[k + 1];
		dist = new int[k + 1];

		for (size_t i = 0; i < k + 1; ++i)
			nodes[i].visited = false;
	}

	~Graph() {

		delete [] dist;
		delete [] nodes;
	}

	void add_node (int from, int to, int value) {
		nodes[from].id = from;
		nodes[to].id = to;

		Edge e = { &nodes[from], &nodes[to], value };
		nodes[from].next.push_back (e);
	}

	int dijkstra (int from, int to) {

		memset (dist, 0x3F3F3F3F, sizeof (int) * (N + 1));

		const compare c1 (dist);
		priority_queue<Node*, deque<Node*>, compare> q (c1);

		dist[from] = 0; 
		
		q.push (&nodes[from]);
		

		while (!q.empty()) {
			Node* t = q.top();
			q.pop();

			for (vector<Edge>::iterator it = t->next.begin(); it != t->next.end(); ++it) {

				it->end->visited = true;
				dist[it->end->id] = min (dist[it->end->id], dist[t->id] + it->value);

				q.push (it->end);
			}
		}

		return nodes[to].visited ? dist[to] : -1;
	}

};

int main() {

	int K, N, M, S, T, A, B, V;

	scanf ("%d", &K);

	for (size_t k = 0; k < K; ++k) {

		scanf ("%d %d %d %d", &N, &M, &S, &T);

		Graph g (N);

		for (size_t m = 0; m < M; ++m) {
			scanf ("%d %d %d", &A, &B, &V);
			g.add_node (A, B, V);
		}

		int out = g.dijkstra (min (S, T), max (S, T));

		if (out == -1) printf ("Case #%d: unreachable\n", k + 1);
		else printf ("Case #%d: %d\n", k + 1, out);

	}

	return 0;
}

[JohnsonWang]

Hi All,

I'm having a similar issue - my submission is returning a TLE, however, it seems to work on all my local test cases just fine. I'm using a simple Dijkstra's, without any real optimisations.

Here is the code:

Code: Select all

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int INF = 9e8;

int get_min_dist( int starting_node, int ending_node, map < int, vector < pair <int, int> > > adj_list, int num_nodes )
{
	vector <int> distances( num_nodes, INF );
	distances[starting_node] = 0;

	priority_queue < pair <int, int> > pq;
	pq.push( make_pair( starting_node, 0 ) );

	while( !pq.empty() )
	{
		pair <int, int> cur = pq.top();
		pq.pop();
	
		vector < pair <int, int> >::iterator it = adj_list[cur.first].begin();
		while( it != adj_list[cur.first].end() )
		{
			if( distances[it->first] > distances[cur.first] + it->second )
			{
				distances[it->first] = distances[cur.first] + it->second;
				pq.push( make_pair( it->first, distances[it->first] ) );
			}
			it++;
		}
	}

	return distances[ending_node];
}

int main()
{
	int num_test_cases;
	cin >> num_test_cases;

	for( int test_case_no = 1; test_case_no <= num_test_cases; test_case_no++ )
	{
		int num_nodes, num_edges, starting_node, ending_node;
		cin >> num_nodes >> num_edges >> starting_node >> ending_node;

		map < int, vector < pair <int, int> > > adj_list;
		for( int edge_no = 0; edge_no < num_edges; edge_no++ )
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			adj_list[from].push_back( make_pair( to, cost ) );
			adj_list[to].push_back( make_pair( from, cost ) );
		}
	
		cout << "Case #" << test_case_no << ": ";
		int dist = get_min_dist( starting_node, ending_node, adj_list, num_nodes );
		if( dist == INF ) cout << "unreachable" << endl;
		else cout << dist << endl;
	}

	return 0;
}

[shanto_0321]

if we scan a='0',then why we do not get the value of a=48-'0'=0.
what is the problem.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
char a[23];
int i,s=0,len;
while(scanf("%s",a)!=EOF)
{
printf("%lld",a);
if((a-48)==0)
             break;
            
      else
{
len=strlen(a);
i=0;
while(a[i]!='\0')
           {          
           s=s+(a[i]-48)*(pow(2,(len))-1);
           i++;
           len--;
           }
printf("%lld",s);
printf("\n");
s=0;
}
}
return 0;
}

[pranon]

Is there something I can do to make my code more efficient? Or does it fall in an infinite loop for some test case?
Any pointers as to how the code can be made more efficient?
Thanks in advance :'(

Code: Select all

Code Edited

[brianfry713]

Doesn't match the sample I/O.

[pranon]

Ok, I'm extremely sorry I posted without removing the...
Ok, here's the code. getting ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
        /*for(i=0; i<n; i++)
            if(seen[i]!=0)
                printf("i= %d, dis = %d\n", i, dis[i]);*/
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while(odd<end && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        temp=heap[min];
        heap[min]=heap[cur];
        heap[cur]=temp;
        iindex[heap[min]]=min;
        iindex[heap[cur]]=cur;
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}

Thanks in advance.

[brianfry713]

I used a C++ STL priority_queue in Dijkstra's algorithm. Is your queue logarithmic?

[pranon]

Yes, I think it takes lg(n) operations to insert, pop and update some node in the worst case. It's an array stored like a heap.
I don't know stl.
I edited my code after getting accepted in 929. But still ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while((odd<end || even<end) && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        if(odd<end)
            min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        else
            min=dis[heap[even]]<dis[heap[cur]]?even:cur;
        if(min!=cur)
        {
            temp=heap[min];
            heap[min]=heap[cur];
            heap[cur]=temp;
            iindex[heap[min]]=min;
            iindex[heap[cur]]=cur;
        }
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}

[brianfry713]

I think your priority queue must be too slow, my code gets AC in 0.22 seconds. If you can't figure out the C++ STL version try using a different implementation. My code doesn't update the queue when a shorter distance to a node is found, it just pushes another item onto the queue.

[mahade hasan]

cut after AC.....

[setu basak]

Code: Select all

#include<bits/stdc++.h>
using namespace std;
vector<int>g[20005];
int cost[20005][20005];
int d[20005];
struct node
{
    int u,w;
    node(int a,int b)
    {
        u=a;w=b;
    }
    bool operator < (const node& p)const
    {
        return w>p.w;
    }
};
void reset()
{
    for(int i=0;i<20005;i++)
        g[i].clear();
}
int dijkstra(int n,int src,int des)
{
    memset(d,63,sizeof(d));
    priority_queue<node>q;
    q.push(node(src,0));
    d[src]=0;
    while(!q.empty())
    {
        node top=q.top();
        q.pop();
        int u=top.u;
        if(u==des)
            return d[des];
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(d[u]+cost[u][v]<d[v])
            {
                d[v]=d[u]+cost[u][v];
                q.push(node(v,d[v]));
            }
        }
    }
    return -1;

}
int main()
{
    int t,edge_number,src,des,cas=1,u,v,delay,n;
    scanf("%d",&t);
    while(t--)
    {
        reset();
        scanf("%d %d %d %d",&n,&edge_number,&src,&des);
        for(int i=0;i<edge_number;i++)
        {
            scanf("%d %d %d",&u,&v,&delay);
            g[u].push_back(v);
            g[v].push_back(u);
            cost[u][v]=delay;
            cost[v][u]=delay;
        }
        int ret=dijkstra(n,src,des);
        if(ret==-1)
            printf("Case #%d: unreachable\n",cas);
        else
            printf("Case #%d: %d\n",cas,ret);
        cas++;
    }
}

[setu basak]

above code give me TLE ..couldn't understand..

[brianfry713]

I made a few optimizations to your code and got it AC in 1.6 seconds. Change reset to only clear g[0] through g[n - 1]. In dijkstra, only set d[0] through d[n - 1] to infinity.