Форум программистов, компьютерный форум CyberForum.ru

Тимус № 1205 - долблюсь уже неделю - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Оператор IF http://www.cyberforum.ru/cpp-beginners/thread219504.html
Функция возводящая в стапень. Последний IF не работает так как нада... #include <iostream> using namespace std; void main() { double ch, st, otv;
C++ Написать программу, работающую с файлами люди, помогите написать программу на файлы. я с++ недавно изучать начал, с файлами еще не разобрался, а задание уже задали..(( завтра уже сдавать( Цель задания Определить принадлежность серии точек прямоугольнику со сторонами, параллельными осям координат Описание На первой строке входного файла указываются координаты главной диагонали прямоугольника. На второй строке указывается количество... http://www.cyberforum.ru/cpp-beginners/thread219501.html
C++ Структуры
#include <iostream> using namespace std; int main() { struct books { char name; int number; char page; };
сформировать неравномерную матрицу C++
Переделать массив 253674 на неравномерную матрицу следующего типа: 22 55555 333 666666 7777777 4444 #include<stdio.h> #include<conio.h>
C++ Ввести строку, вывести на экран только слова, имеющие заданную длину. http://www.cyberforum.ru/cpp-beginners/thread219495.html
Ввести строку, вывести на экран только слова, имеющие заданную длину. Не получается сделать программу без косяков, очень маленький опыт работы в С Помогите пожалуйста с программой.
C++ Циклы в Cи Всем привет, в общим столкнулся с проблемой, мне необходимо пробежаться по одной и той же строчке содержащею цифры например 1,2,3,4,5... Циклы должны бежать так чтобы: first=1; second=2; потом first=1; second=3; и так до конца, далее first=2; second=3; потом first=2; second=4; и так до конца, надеюсь объяснил себя понятно) Помогите пожалуйста. подробнее

Показать сообщение отдельно
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579

Тимус № 1205 - долблюсь уже неделю - C++

24.12.2010, 17:35. Просмотров 985. Ответов 2
Метки (Все метки)

Ссылка на задачу

Решение вроде правильное, но программа упорно падает на тесте 7 (WA). Что за косяк может быть?

Суть решения: Создаем полный граф, в котором длина ребра между станциями, соединенными метро - расстояние между ними, деленное на скорость метро. Все остальные ребра (станции, не соединенные метро, а также начальная и конечная точки) равны расстоянию между точками, деленное на скорость пешком. Затем Дейкстрой проходим по графу из исходной точки, и выводим в качестве ответа результат работы Дейкстры в конечной точке. Естественно, записывая при этом маршрут прохода по графу, исключая начальную и конечные точки.

Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
struct point{double x; double y;};
 
long double foot, metro;
int N;
point F[213];
long double gr[213][213];
long double dp[213];
bool f[213];
int r[213];
 
double GetRasst(point a, point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
 
void Dijkstra()
{
    memset(r,0,sizeof(r));
    int u=N-1;
    r[u]=-1;
    for (int i=1;i<=N;i++) { dp[i]=100000000; f[i]=true;}
    dp[u]=0;
    for (int i=1;i<=N;i++)
    {
        long double mn=100000000;
        for (int j=1;j<=N;j++)
            if (dp[j]<=mn && f[j]) {u=j; mn=dp[j];}
        for (int j=1;j<=N;j++)
        if (gr[u][j]>0)
            if (dp[j]>dp[u]+gr[u][j]) { r[j]=u; dp[j]=dp[u]+gr[u][j];}
        f[u]=false;
    }
 
 
}
int main()
{
    memset(gr,0,sizeof(gr));
    cin >> foot >> metro;
    cin >> N;
    for (int i=1;i<=N;i++)
        cin >> F[i].x >> F[i].y;
    int a,b;
    cin >> a >> b;
    while (a!=0 && b!=0)
    {
        gr[a][b]=GetRasst(F[a], F[b])/metro;
        gr[b][a]=gr[a][b];
        cin >> a >> b;
    }
    cin >> F[N+1].x >> F[N+1].y;
    cin >> F[N+2].x >> F[N+2].y;
    N+=2;
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            if (gr[i][j]==0 && i!=j)
            { gr[i][j]=GetRasst(F[i], F[j])/foot; gr[j][i]=gr[i][j];}
    Dijkstra();
    cout.setf(ios::fixed);
    cout.precision(7);
    if (F[N].x!=F[N-1].x || F[N].y!=F[N-1].y)
    {
        cout << dp[N] << endl;
        vector<int> rt;
        int G=N;
        while (r[G]!=-1) {if (r[G]!=N && r[G]!=N-1)rt.push_back(r[G]);G=r[G];}
        cout << rt.size() << ' ';
        for (int i=rt.size()-1;i>=0;i--) cout << rt[i] << ' ';
    }
    else
    {
        double a=0;
        cout << a << endl;
        cout << 0;
    }
    return 0;
}
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru