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

Жадный граф/алгоритм - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Преобразование строки в число http://www.cyberforum.ru/cpp-beginners/thread1152601.html
Вот код из учебника #include<iostream> using std::cout;using std::endl; int main(){ char str="0123456789"; const int SIZE=10; int arr={0}, index=0; for (char *p=str; *p;++p){ if (*p>='0' && *p<='9') { arr=*p-'0';//вычитаем код символа числа ноль получаем искомое число
C++ Создайте класс name, методы класса с файловым вводом/выводом данных #include <iostream> #include <string> #include <fstream> #include <locale.h> using namespace std; int kol; int cl = 0; http://www.cyberforum.ru/cpp-beginners/thread1152591.html
C++ Программа, которая вычисляет длину введенной с клавиатуры строки
Ребят помогите и объясните пожалуйста :wall::cry: Нужно написать программу, которая вычисляет длину введенной с клавиатуры строки. p.S. Находил подобную тему на форуме, но не разобрался в программе...=((((
Дан файл состоящий из строк которые могут начинаться C++
дан файл состоящий из строк которые могут начинаться либо с русских либо с английских слов.записать в другой файл только те строки которые начинаются с русских слов. программа на Turbo C++. помогите,, нужно на завтра.
C++ Исправить регулярку, чтобы в rgxm записывалось последовательно логин, пароль, адрес сервера, порт и имя потока http://www.cyberforum.ru/cpp-beginners/thread1152548.html
Пытаюсь распарсить выражение такого вида "rtsp://@]<server-address-or-name>" result = std::regex_match(url, rgxm, std::regex("rtsp://(\\w*):*(\\w*)@*(*):*(\\d*)(*)")); Но если отсутсвует логин и пароль, то не верно определяется адрес сервера (ip-address) (первые цифры идут в логин, пароль пустой и соотвестнно адрес не верно определен) Как можно исправить регулярку, чтобы в rgxm...
C++ Ссылка на переменную другого класса Всем привет ! Хочу создать ссылку на переменную класса Animation. class PLAYER { public: .... float &CURRENTFrame; подробнее

Показать сообщение отдельно
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.04.2014, 22:38     Жадный граф/алгоритм
UraNick, обычная Дейкстра(если веса рёбер положительны), или Форд-Беллман(а там уже всё равно, какие веса).Только оптимизируйте не на наименьший вес, а на наибольший - там просто знак местами поменять. Вот вам алгоритм Дейкстры:
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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
const int maxe=100,maxv=100;
int ef[maxe],es[maxe],ev[maxe],next[maxe],first[maxv],c=0,i;
vector<long long> d(maxv+1,100000000),p(maxv+1);
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
 
 
void add(int v1,int v2,int value)
{
    next[++c]=first[v1];first[v1]=c;
    ef[c]=v1;es[c]=v2;ev[c]=value;
}
 
void init()
{
    int x,y,z;
    for(i=0;i<5;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
}
 
void dist()
{
    int s=1;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int to=q.top().second;int line=q.top().first;
        q.pop();
        if(line>d[to])  continue;
        for(int h=first[to];h;h=next[h])
            if(line+ev[h] < d[es[h]])
            {
                d[es[h]]=line+ev[h];
                p[es[h]]=to;
                q.push(make_pair(d[es[h]],es[h]));
            }
    }
}
 
int main()
{
    init();
    dist();
    cout<<d[2]<<endl;
    system("pause");
    return 0;
}
вот Форд
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
//Надо помнить, что если рёбра двунаправлены, то бежать по 2*m.
//И если нужно найти цикл, то просто делаем ещё 1 проход, и фиксируем булевой переменной
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
 
using namespace std;
typedef long long ll;
 
const ll maxv=100,maxe=10000;
ll ef[maxe],es[maxe],ev[maxe],first[maxv],next[maxe],c=0;
ll n,m,i,j,k,x,y,z,s;
vector<ll> d(maxv,100000000);
void init(ll v1,ll v2,ll val)
{
    next[++c]=first[v1];first[v1]=c;
    ef[c]=v1;es[c]=v2;ev[c]=val;
}
 
void ford()
{
    d[s]=0;
    for(i=1;i<n;++i)
    {
        for(j=1;j<=m;++j)
        {
            if(d[ef[j]]+ev[j]<d[es[j]])
                d[es[j]]=d[ef[j]]+ev[j];
        }
    }
}
 
void sol()
{
    cin>>n>>m>>s;
    for(i=0;i<m;++i)
    {
        cin>>x>>y>>z;
        init(x,y,z);
    }
    ford();
}
 
int main()
{
    sol();
    cout<<d[2]<<endl;
    system("pause");
    return 0;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru